Тема ТЕОРИЯ ЧИСЕЛ

Делимость и делители (множители)

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела теория чисел

Разделы подтемы Делимость и делители (множители)

Условия про НОД и НОК

Разложение на множители, основная теорема арифметики

Количество, сумма, произведение делителей

Степени вхождения простых

Оценки для доказательства делимости

Алгоритм Евклида

Теоретико-числовые свойства биномиальных коэффициентов

Теоретико-числовые свойства чисел Фибоначчи

Целые гауссовы числа

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 201#101215Максимум баллов за задание: 7

Определите все пары натуральных чисел $n$ и $m,$ для которых числа $n2+ 4m$ и $m2+ 5n$ являются квадратами.

Показать ответ и решение

Разберем два случая. Сначала предположим, что $m ≤n.$ Тогда

2 2 2 2 n < n +4m ≤ n +4n <(n+ 2)

Следовательно, $n2+4m = (n +1)2,$ откуда $4m = 2n +1,$ что невозможно из соображений четности.

Теперь предположим, что $n < m.$ Тогда

2 2 2 2 m <m + 5n < m + 6n< (m + 3)

Следовательно, либо $m2 + 5n= (m + 1)2,$ либо $m2+ 5n= (m+ 2)2,$ откуда либо $5n= 2m+ 1,$ либо $5n= 4m+ 4.$ Изучим каждый из этих подслучаев отдельно.

Если $5n= 2m + 1,$ то $4m =10n− 2$ и число $n2 +4m = n2+10n− 2$ является квадратом, тогда

2 2 2 n < n + 10n − 2< n + 10n +25

Это квадрат числа, большего $n$ и меньшего $n+ 5,$ той же четности, что и $n.$ Следовательно, либо

n2 +10n− 2= (n +2)2 = n2+4n +4,

либо

n2+ 10n− 2= (n +4)2 = n2+8n+ 16

В итоге или $n= 1$ и $m = 2,$ или $n= 9$ и $m =22.$

Если же $5n =4m +4,$ то $4m = 5n− 4$ и число $n2+ 4m =n2 +5n− 4$ является квадратом, значит,

n2 < n2+ 5n− 4< n2+6n+ 9

Это квадрат числа, большего $n$ и меньшего $n+ 3.$ Следовательно, либо

n2+ 5n − 4 =n2+ 2n+ 1,

либо

2 2 n + 5n− 4= n +4n+ 4

Первое уравнение имеет нецелый корень, а второе дает $n = 8,$ откуда $m = 9.$

Все полученные ответы подходят.

Ответ:

$(m,n)∈ {(2,1), (22,9), (9,8)}$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 202#141563Максимум баллов за задание: 7

Определите все натуральные числа $n,$ имеющие ровно $√n-$ натуральных делителей (включая $1$ и само число $n).$

Источники: Курчатов - 2019, 10.3 (см. olimpiadakurchatov.ru)

Показать ответ и решение

Во-первых, заметим, что $n =1$ подходит, и будем считать, что $n≥ 2.$ Во-вторых, из условия следует, что $n= k2$ для некоторого натурального $k.$ Квадраты натуральных чисел имеют нечётное количество делителей, поскольку все делители, кроме основания квадрата, разбиваются на пары вида $d$ и $n∕d.$ Таким образом, $k$ — нечётное число, большее $1.$

Пусть $k = 2m + 1$ для некоторого натурального $m.$ Число $n$ имеет $m$ делителей, меньших $k,$ и $m$ делителей, больших $k,$ причём все делители нечётны. Это означает, что $n$ делится на все нечётные натуральные числа, меньшие $k,$ поскольку их ровно $m.$

В частности, $2 k$ делится на $k − 2.$ Поскольку $2 k − 4 =(k− 2)(k+ 2)$ тоже делится на $k− 2,$ то и разность $2 2 4= k − (k − 4)$ кратна числу $k− 2.$ Осталось заметить, что $k− 2$ — нечётный делитель числа $4,$ то есть $k − 2= 1,$ откуда $k= 3$ и $n =9.$

Ответ:

$1$ и $9$

Ошибка.
Попробуйте повторить позже

Задача 203#32933Максимум баллов за задание: 7

Может ли сумма объёма, длин всех рёбер и площадей всех граней некоторого прямоугольного параллелепипеда, длины рёбер которого являются целыми числами, равняться $866?$

Источники: Всесиб-2018, 11.3 (см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Давайте для начала введём неизвестные (скажем, стороны это a,b,c) и попробуем записать сумму из условия через эти неизвестные. По условию эта сумма равна 866

Подсказка 2

Так, Вы должны были получить abc+4(a+ b+c)+ 2(ab+ bc+ ac)=866. Теперь полезно разложить на множители левую часть уравнения. Нужно добавить такое число, чтобы левая часть хорошо свернулась на симметричные относительно a,b,c скобочки. Ну же, не зря мы ботали тождественные преобразования!

Подсказка 3

Добавить нужно 8. У Вас должно получиться (а+2)(b+2)(c+2) = 2*437. Осталось совсем чуть-чуть, подумайте над этим равенством в терминах разложения на множители!

Показать ответ и решение

Пусть длины сторон $a,b,c.$ Они положительные (как длины сторон) и целые (по условию), значит, натуральные. Сумма объёма, длин всех рёбер и площадей всех граней равна $866,$ то есть:

abc+ 4(a +b+ c)+2(ab +bc+ ac)= 866

3 (a+2)(b+ 2)(c+ 2)=866+ 2 = 2⋅437

Правая часть является произведение простых чисел $2,19$ и $23,$ так что по основной теореме арифметики следует, что это единственное разложение данного числа в произведение трёх натуральных чисел, больших единицы, и одно из них равно $2.$ Однако левая часть уравнения является произведением трёх натуральных чисел, каждое из которых не меньше трёх, что приводит к противоречию. Следовательно, равенство из условия задачи невозможно.

Ответ:

нет

Ошибка.
Попробуйте повторить позже

Задача 204#39355Максимум баллов за задание: 7

По определению $n!= 1⋅2⋅3⋅...⋅n$ . Является ли выражение $1008!⋅1009!⋅2017!⋅2018!$ квадратом натурального числа?

В ответ внесите “да” или “нет”.

Подсказки к задаче

Подсказка 1

Давайте попробуем преобразовать наше выражение в более удобный вид, где мы сразу поймём квадрат это или нет. У нас есть две пары соседних факториалов. Как тогда можно записать их по-другому?

Подсказка 2

Верно, можем записать 1009! в виде 1008!*1009, а 2018! — 2017!*2018. Тогда у нас получаются два факториала в квадрате умножить на 1009 и 2018. Может ли такое число быть квадратом?

Подсказка 3

Верно, раскладывая ещё эти числа на множители мы получаем квадрат, умноженный на 2. Теперь понятно, что это число не может быть полным квадратом. Победа!

Показать ответ и решение

Заметим, что

2 1008!⋅1009!= (1008!) ⋅1009

2 2017!⋅2018!= (2017!) ⋅2018

Получаем, что

1008!⋅1009!⋅2017!⋅2018!=(1008!)2⋅(2017!)2⋅1009⋅2018= (1008!⋅2017!⋅1009)2⋅2

Число вида $2a2$ не может быть точным квадратом по основной теореме арифметике, ведь степень вхождения множителя $2$ в число $2a2$ всегда нечётна.

Ответ: нет

Ошибка.
Попробуйте повторить позже

Задача 205#39356Максимум баллов за задание: 7

Числа от $1$ до $50$ написаны на карточках. Можно ли разложить эти карточки в $11$ мешков (чтобы в каждый мешок попала хотя бы одна карточка) так, чтобы в каждом мешке произведение чисел на карточках делилось на $9$ ?

В ответ внесите “да” или “нет”.

Подсказки к задаче

Подсказка 1

Давайте, прочитав условие, поймём, а когда вообще произведение чисел в мешке будет делиться на 9? Какие возможны варианты?

Подсказка 2

Верно, нужно, чтобы в мешке либо было число делящееся на 9, либо два числа делящиеся на 3. Но таких чисел от 1 до 50 явно не много. Попробуйте посчитать, сколько их.

Подсказка 3

Ага, у нас получается пять чисел, кратных 9, и 11 чисел, кратных 3, но не кратных 9. Но получится ли тогда у нас раскидать их по мешкам, чтобы соблюдалось условие? Проверьте это, и задача решена!

Показать ответ и решение

Чтобы произведение чисел на карточках делилось на $9$ , то в мешке либо должна быть хотя бы одна карточка, число на которой делится на $9$ , либо хотя бы две карточки, числа на которых делятся на $3$ , но не делятся на $9$ . Среди чисел от $1$ до $50$ есть пять чисел кратных $9$ — $9$ , $18$ , $27$ , $36$ и $45$ . Их хватит на не более чем пять мешков. Чисел от $1$ до $50$ , которые кратны $3$ , но не кратны $9$ , всего $11$ — $3$ , $6$ , $12$ , $15$ , $21$ , $24$ , $30$ , $33$ , $39$ , $42$ , $48$ . Этих чисел также хватит не более чем на пять мешков. Получается, что максимум в десяти мешках произведение чисел может делиться на $9$ — противоречие.

Ответ: нет

Ошибка.
Попробуйте повторить позже

Задача 206#39358Максимум баллов за задание: 7

Найдите все такие пары натуральных чисел $a$ и $b$ , что

Н ОК(a,b)= НОД (a,b)+ 19

и докажите, что других нет.

Источники: Школьный этап - 2018, Москва, 9.5

Подсказки к задаче

Подсказка 1

Давайте сразу обратим внимание на число 19 в правой части. Нам повезло — оно простое! Тогда хорошо бы задуматься о делимости.

Подсказка 2

Ага, d — это наименьший делитель a и b, а значит, и нок на него делится. Какой тогда вывод про d отсюда можно сделать?

Подсказка 3

Верно, так как тогда и 19 должно делиться на d, а оно простое, то d равен либо 1, либо 19. Теперь осталось только аккуратно разобрать два случая. Не забудьте, что если d равен 19, то a и b минимум равны 19.

Показать ответ и решение

Обозначим за $d$ наибольший общий делитель чисел $a$ и $b$ . Очевидно, что и НОД, и НОК делятся на $d$ . Это означает, что $19= НО К(a,b)− Н ОД(a,b)$ тоже делится на $d$ . Тогда $d$ может быть равен только $1$ или $19$ .

Если $d= 1$ , то тогда $ab= НОК (a,b)=Н ОД(a,b)+ 19 =20$ . Отсюда, небольшим перебором, получаем, что $a$ и $b$ могут быть равны $(1,20)$ , $(20,1)$ , $(4,5)$ , $(5,4)$ .

Если же $d =19$ , то тогда $НОК (a,b)=Н ОД(a,b)+ 19 =38$ . С одной стороны и $a$ , и $b$ не меньше чем $d$ , поэтому они оба хотя бы $19$ . С другой стороны они оба не больше чем $Н ОК(a,b)= 38$ . Причём оба числа должны делиться на $19$ . То есть $a$ и $b$ могут быть только числами $(19,38)$ или $(38,19)$ .

Ответ:

$(1,20)$ , $(20,1)$ , $(4,5)$ , $(5,4)$ , $(19,38)$ , $(38,19)$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 207#72736Максимум баллов за задание: 7

В таблице $4× 4$ расставлены $16$ различных натуральных чисел. Для каждой строки и каждого столбца таблицы нашли наибольший общий делитель расположенных в нем чисел. Оказалось, что все найденные восемь чисел различны. Для какого наибольшего $n$ можно утверждать, что в такой таблице найдется число не меньше $n?$

Источники: Иннополис-2018

Подсказки к задаче

Подсказка 1

Давайте для начала удобно переформулируем условие задачи. Если все НОДы различные, то какое наименьшее значение оно может принимать?

Подсказка 2

Верно, так как столбцов и строк в сумме 8, то и наименьшее значение НОДа равно 8. Давайте теперь посмотрим на одну строку или столбец, и пусть НОД чисел равен d. Тогда какое наименьшее число может быть в этой строке?

Подсказка 3

Ага, так как все числа различны, то и наименьшее число будет хотя бы 4d. Тогда совмещая эти два условия, находим, какое в принципе наименьшее число возможно на доске. Это 32. Теперь вспомним, что различные числа у нас расставляются произвольно. Поэтому осталось только придумать пример, в котором все числа будут не больше 32. То есть это будет вашим контрпримером, что больше 32 число взять нельзя. Победа!

Показать ответ и решение

Если в каком-то ряду наибольший общий делитель равен $n,$ то в нем есть четыре числа, делящихся на $n,$ a, значит, число, не меньшее, чем $4n.$ Поскольку наибольшие общие делители во всех рядах различны, один из них заведомо не меньше $8.$ Тогда в соответствующем ему ряду должно быть число, не меньшее $32.$ Приведем теперь пример таблицы, в которой все числа не больше $32.$ Наибольшие общие делители по строкам равны $5,6,7$ и $8,$ а по столбцам равны $1,2,3$ и $4.$


5	10	15	20

30	6	18	12

7	14	21	28

8	16	24	32

Замечание. Наибольшие общие делители заведомо должны быть числами от $1$ до $8,$ а ряды с НОДами $6,7$ и $8$ должны быть составлены из тех чисел, которые стоят в соответствующих рядах в таблице из примера (возможно в другом порядке).

Ответ: 32

Ошибка.
Попробуйте повторить позже

Задача 208#73687Максимум баллов за задание: 7

Найдите все четные натуральные числа $n,$ у которых число делителей (включая $1$ и само $n$ ) равно $n. 2$ (Например, число $12$ имеет $6$ делителей: $1,2,3,4,6,12.$ )

Подсказки к задаче

Подсказка 1

Попробуйте оценить сверху количество делителей числа n.

Подсказка 2

Пусть pq = n и p ≤ q. Какую верхнюю оценку можно сделать на p? Как из нее вывести оценку на количество делителей?

Подсказка 3

Правильно! p ≤ √n, а, значит, делителей p ≤ 2√n. Осталось только решить неравенство n/2 ≤ 2√n и перебрать случаи.

Показать ответ и решение

Все делители числа $n$ разбиваются на пары $(d,n),d ≤ n . d d$ Заметим, что $d≤ √n,$ поскольку $n = d⋅ n≥ d2. d$ Но тогда понятно, что количество таких пар не превосходит $√ - [ n],$ а количество делителей $n$ — не больше $√- 2[n].$ В данном случае нам хватит оценки $√- 2 n.$

По условию количество делителей равно $n 2.$ Следовательно, получим неравенство $n √ - 2 ≤ 2 n.$ Решая его в натуральных числах, получаем, что $n ≤16.$ Перебирая чётные $n,$ находим подходящие $n= 8$ и $n= 12.$

Ответ:

$8,12$

Ошибка.
Попробуйте повторить позже

Задача 209#82709Максимум баллов за задание: 7

Найдите такое наименьшее натуральное число, что его половина есть пятая степень некоторого целого числа, а пятая часть есть квадрат некоторого целого числа.

Источники: ПВГ 2018

Подсказки к задаче

Подсказка 1

Запишите условие задачи в форме системы уравнений.

Подсказка 2

Воспользуйтесь тем, что 2 и 5 — взаимно простые числа.

Подсказка 3

Проанализируйте делимость искомого числа на 2 и 5 и представьте его в виде 2ᵏ5ᵐtⁿ.

Показать ответ и решение

Пусть $n$ — число, удовлетворяющее условию задачи. Тогда существуют такие целые числа $p$ и $s,$ что верна система

{ 1n =p5 21 2 5n =s

Умножаем на $2$ и $5$ соответственно первое и второе уравнение. Система приобретает вид

{ n =2p5 n =5s2

Из первого получаем, что $n ... 2.$ Тогда из второго уравнения, так как числа 2 и 5 взаимно просты, следует, что $s2 ... 2,$ то есть $s ... 2,$ и, стало быть, $. n .. 4.$ Аналогично получаем, что $. 55.. n.$

Пусть $n= 22 ⋅55k.$ Подставим в систему

{ 22⋅55k = 2p5 22⋅55k = 5s2

Сокращаем на 2 и 5 уравнения соответственно

{ 2⋅55k= p5 22⋅54k= s2

Из первого уравнения получаем, что $2 ... p,$ следовательно, $k ... 24.$ Наименьшее $k,$ удовлетворяющее этому условию равно $4 2 .$ Пусть $4 k= 2 ,$ тогда $6 5 n = 2⋅5 .$ Видим, что оно удовлетворяет системе, значит, это и есть нужное минимальное число.

Ответ:

$26⋅55$

Ошибка.
Попробуйте повторить позже

Задача 210#82710Максимум баллов за задание: 7

Найдите натуральное число, делящееся на 225 и имеющее 15 различных делителей.

Подсказки к задаче

Подсказка 1

Запишите число в виде разложения на множители, вспомните про формулу количества делителей числа.

Подсказка 2

Число делителей равно 15 с одной стороны, а с другой (3+k)(3+m)s, надо оценить правую часть.

Подсказка 3

3+k ≥ 3, 3+m ≥ 3, какие значения могут принимать k,m,s?

Показать ответ и решение

Заметим, что $225 =32⋅52.$ Пусть $n$ — число, которое мы ищем. Тогда $n =32+k⋅52+t⋅s,$ где $k$ и $t$ — неотрицательные целые числа, а $s$ — натуральное, не делящееся на $3$ и $5$ .

Пусть $r$ — число делителей $s,$ Заметим, что число $n$ имеет $(2+ k+ 1)(2+ t+1)r$ делителей. Так как всего делителей у нас $15,$ то получаем уравнение

(3+ k)(3+ t)r= 15

Так как $3+ k≥ 3$ и $3+t≥ 3,$ а также $15 =3⋅5,$ то либо $k= 0$ и $t= 2,$ либо $k= 2$ и $t =0.$ Таким образом, $n = 32⋅54$ или $4 2 n =3 ⋅5 .$

Ответ:

$n =32⋅54$ или $n= 34⋅52.$

Ошибка.
Попробуйте повторить позже

Задача 211#85844Максимум баллов за задание: 7

Старательный Роберт выписывает на доску все пары, состоящие из трехзначного и четырехзначного чисел, такие, что каждое из этих чисел делится на их разность. Сколько пар выпишет на доску Роберт?

Источники: Лига открытий - 2018

Показать ответ и решение

Рассмотрим произвольную пару, выписанную Робертом. Обозначим разность в ней через $x.$ Тогда сами числа равны $nx$ и $(n+1)x$ при некотором натуральном $n.$ При этом число $nx$ должно быть трехзначным, а $(n +1)x$ — четырехзначным. Заметим, что при $x≥ 1000$ такое невозможно. Если же $1 ≤x ≤999,$ то такое $n$ обязательно найдется, и более того, оно единственно: подходит наибольшее $n,$ при котором $nx <1000.$ Число $nx$ в таком случае трехзначно, ведь будь оно двузначно, мы могли бы увеличить $n$ хотя бы на $1.$ При этом число $(n+ 1)x ≥1000,$ но при этом, очевидно, не больше $1998,$ так как $x ≤999.$ Остальные $n,$ очевидно, не подходят: при больших значениях $n$ число $nx$ уже не трехзначно, а при меньших число $(n+ 1)x$ не четырехзначно.

Итак, при любом $1≤ x≤ 999$ существует ровно одна пара с разностью $x,$ подходящая под условие, а при остальных $x$ таких пар нет вообще. Значит, пар $999.$ Все они различны хотя бы потому, что в этих парах разная разность чисел в паре.

Ответ:

$999$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 212#88132Максимум баллов за задание: 7

Найдите все чётные натуральные числа $n$ , у которых число делителей (включая 1 и само $n$ ) равно $n 2$ . (Например, число 12 имеет 6 делителей: $1,2,3,4,6,12$ .)

Подсказки к задаче

Подсказка 1

Подумаем, а что мы вообще знаем о количестве делителей? Быть может, можно его как-то оценить, чтобы ограничить n?

Подсказка 2

Заметим, что делители делятся на пары, в каждой из которых хотя бы одно числа не превосходит sqrt(n). Как тогда оценить количество делителей сверху?

Подсказка 3

Количество делителей н превосходит 2*sqrt(n)! Что тогда можно сказать про n?

Подсказка 4

n не превосходит 16! Осталось лишь понять, какой вид имеет число при разложении на простые и понять, какие степени простых могут в него входить ;) А чему равно количество делителей?

Подсказка 5

Количество делителей равно произведению степеней, в которых простые числа входят в n, увеличенных на единицу!

Показать ответ и решение

Если $d$ — делитель числа $n$ , то $n d$ — тоже делитель числа $n$ . Хотя бы одно из этих двух чисел не превосходит $√n.$ Поэтому число делителей не превосходит $√- 2 n.$

По условию число делителей равно $n 2.$ Следовательно, $n √- 2 ≤2 n =⇒ n ≤16.$

Разложим число $n$ на возможные простые множители:

a b c d n= 2 ⋅3 ⋅5 ⋅7

Из условия на количество делителей

(a+ 1)(b+1)(c+ 1)(d+ 1)= n= 2a−1⋅3b⋅5c⋅7d 2

следует, что при $a +1≥ 5$ правая часть строго больше левой:

a−1 b c d 2 >a +1, 3 ≥ b+1, 5 ≥ c+ 1, 7 ≥d+ 1.

Поэтому и каждая из скобок в левой части меньше 5, так что $5c = 1,7d =1,$ остаётся перебрать три случая в равенстве

a−1 b (a+ 1)(b+1)= 2 ⋅3.

$a =1$ быть не может, так как тогда левая часть чётна, а правая часть нечётна.
при $a= 2$ единственным решением $3(b+ 1)= 2⋅3b$ является $b= 1 =⇒ n =12.$
при $a= 3$ единственным решением $4(b+ 1)= 4⋅3b$ является $b= 0 =⇒ n =8.$

Ответ: 8 и 12

Ошибка.
Попробуйте повторить позже

Задача 213#88134Максимум баллов за задание: 7

Найдите наименьшее натуральное число, имеющее ровно 42 натуральных делителя (включая единицу и само число).

Подсказки к задаче

Подсказка 1

Подумаем, а что мы вообще знаем о количестве делителей?

Подсказка 2

Количество делителей равно произведению степеней, в которых простые числа входят в число (пусть M), увеличенных на единицу! Тогда рассмотрим разложение M и составим уравнение по условию!

Подсказка 3

Пусть простые делители входят в M в степенях k₁, k₂, …, kₙ. Тогда (k₁+1)(k₂+1)…(kₙ+1) = 42. Остается лишь разобрать случаи ;)

Показать ответ и решение

Пусть $n$ — искомое натуральное число, разложим на простые:

k1 k2 km n =p1 ⋅p2 ⋅...⋅pm

Любой натуральный делитель этого числа имеет вид

l1 l2 lm d= p1 ⋅p2 ⋅...⋅pm

где $li ∈{0,1,...,ki},i= 1,...,m$ . Число делителей числа $n$ равно

(k1+1)(k2+1)⋅⋅⋅(km+ 1)= 42.

Разложим число 42 на неединичные сомножители всеми возможными способами и выберем из них наименьшее $n.$ Поскольку $42= 2⋅3⋅7$ , то имеем пять случаев:

1) $42 =42$ , наименьшее число $n =241 > 3000$ ;

2) $42 =21⋅2$ , наименьшее число $n =220⋅31 >3000$ ;

3) $42 =14⋅3$ , наименьшее число $n =213⋅32 >3000$ ;

4) $42 =7⋅6$ , наименьшее число $n =26⋅35 = 64⋅243 >3000$ ;

5) $42 =7⋅3⋅2$ , наименьшее число $n =26⋅32⋅51 = 2880$ .

Ответ: 2880

Ошибка.
Попробуйте повторить позже

Задача 214#88136Максимум баллов за задание: 7

Найти натуральное число $N$ , содержащее простыми множителями только 2, 5 и 7, зная, что:

1) $5N$ имеет на 8 делителей больше, чем $N$ ;

2) $7N$ имеет на 12 делителей больше, чем $N$ ;

3) $8N$ имеет на 18 делителей больше, чем $N$ .

Подсказки к задаче

Подсказка 1

Неважно, что даны простые делители именно 2, 5 и 7, важно только, что их ровно три различных. Вспомним волшебную формулу из веба, которая определяет число делителей, зная степени вхождения всех простых!

Подсказка 2

После применения формулы к трем условиям нашей задачи получим три уравнения с тремя неизвестными. После упрощения система приобретает вид: uv=a, vw=b, uw=c. Такие системы встречаются довольно часто, и решаем мы их, перемножив все три выражения, а далее, подставляя полученное значение uvw в изначальные уравнения, находим оттуда u, v, w.

Показать ответ и решение

Число $N$ имеет вид: $N =2x⋅5y⋅7z$ . Число его делителей по известной формуле равно $(x+ 1)(y+ 1)(z+ 1)$ . Число $5N = 2x ⋅5y+1⋅7z$ и число его делителей равно: $(x+ 1)(y+2)(z+1)$ . Согласно условию:

(x+ 1)(y+ 2)(z+ 1)− (x+ 1)(y+1)(z +1)= 8

или $(x+ 1)(z+ 1)=8$ . Число $7N = 2x⋅5y⋅7z+1$ . Аналогично предыдущему, получим: $(x+ 1)(y+1)= 12$ . Наконец, $8N = 2x+3⋅5y⋅7z$ , откуда найдем: $3(y+ 1)(z+ 1)=18$ или: $(y+ 1)(z+ 1)=6$ .

Получили систему трех уравнений с тремя неизвестными, которая обычно решается так. Перемножив три уравнения системы, найдем

2 2 2 (x+ 1) (y +1) (z+ 1) =8⋅12⋅6

откуда

(x+ 1)(y+1)(z +1)= 24.

Деля это уравнение последовательно на первое, второе и третье уравнение системы, получим: $y+ 1= 3;z +1 =2;x+ 1= 4$ . Отсюда: $x =3;y = 2;z =1$ . Следовательно,

N = 23⋅52⋅7= 1400.

Ответ: 1400

Ошибка.
Попробуйте повторить позже

Задача 215#95564Максимум баллов за задание: 7

Число $1 + 1 + 1+ 1+ ...+ 1- 2 3 4 444$ записано в виде несократимой дроби. На сколько нулей оканчивается знаменатель этой дроби?

Источники: Лига открытий - 2018

Показать ответ и решение

Приведем все дроби к общему знаменателю, не складывая числители и не сокращая. Он будет иметь вид $28⋅53⋅x,$ где $x$ не делится ни на $2,$ ни на $5.$ Дробь $-1- 256$ добавит нечетный числитель, остальные дроби добавят четные числители. Дроби $-1- 1-- 125,250$ и $-1- 375$ дают в сумме $-1- 11 125 ⋅ 6 ,$ поэтому их сумма добавит к числителю одно слагаемое, не кратное пяти. Остальные слагаемые будут кратны пяти. Следовательно, полученный после сложения числитель не делится ни на $2,$ ни на $5.$ Следовательно, знаменатель содержит ровно три нуля.

Ответ:

$3$

Ошибка.
Попробуйте повторить позже

Задача 216#95764Максимум баллов за задание: 7

Вася выписывает произведения соседних натуральных чисел: $1⋅2,2⋅3,3⋅4,...,$ $99⋅100.$ Сколько из полученных чисел будут делиться на $6$ без остатка?

Источники: Лига открытий - 2018

Показать ответ и решение

Каждое из данных произведений делится на $2,$ поэтому достаточно определить, сколько из них делятся на $3.$ Каждое число кратное трем входит в два произведения, поэтому количество искомых произведений $33⋅2= 66.$

Ответ:

$66$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 217#105487Максимум баллов за задание: 7

Для натурального числа $n$ на доску выписали числа

-0 -1-- ---n−-1- n ,n− 1,...,n − (n− 1)

Пусть $d$ — некоторый натуральный делитель $n.$ Докажите, что на доске встретится число $d− 1.$

Подсказки к задаче

Подсказка

Запишите n как kd и попробуйте подобрать такую дробь, чтобы после сокращения получилось d - 1.

Показать доказательство

Пусть $n =kd.$ Тогда на доске присутствует дробь

n−-k kd-− k k = k =d − 1

что и требовалось

Ошибка.
Попробуйте повторить позже

Задача 218#61644Максимум баллов за задание: 7

Найдите все натуральные числа $n$ от $1$ до $100$ включительно такие, что если перемножить все делители числа $n$ (включая $1$ и $n$ ), получим число $3 n .$

Подсказки к задаче

Подсказка 1

Хочется как-то в общем виде записать, чему равно произведение всех делителей. Мы знаем, что в большинстве случаев делители можно разбить на пары (потому что если у числа n есть делитель k, то есть также делитель n/k), но у некоторых чисел есть лишь нечетное количество делителей. Что это за числа?

Подсказка 2

Если число является точным квадратом, то оно имеет нечётное число делителей! Подойдёт ли нам какой-то из точных квадратов?

Подсказка 3

Пусть у точного квадрата n кроме делителя √n есть еще s пар делителей. Заметим, что произведение делителей в каждой паре равно n, тогда произведение всех делителей равно n^(s+1/2) = n³, а это верно только при n = 1.

Подсказка 4

Теперь рассматриваем числа, имеющие s пар делителей, чему равно произведение делителей в этом случае? Можем ли мы понять, сколько делителей должно быть у нашего числа?

Подсказка 5

Так как n^s = n³, у нашего числа есть всего 6 делителей! Давайте попробуем понять, сколько простых чисел может быть делителями числа n, может ли у n быть больше двух простых делителей?

Подсказка 6

Нет, у n есть максимум два простых делителя! Ведь если бы n делилось на р₁, р₂ и р₃, то у него были бы делители р₁р₂, р₁р₃ и р₂р₃, а так как делителей всего шесть, среди этих чисел есть число 1, что невозможно, ведь 1 не является простым числом. Таким образом, мы можем разложить n на простые множители и перебрать все возможные варианты.

Подсказка 7

Получаем, что n = p⁵ или n = р₁р₂². В первом случае легко угадываем пятую степень некоторого числа, не превосходящую 100, а во втором вариантов будет гораздо больше! Так как р₁ ≥ 2, р₂² ≤ 100/2 = 50, отсюда получаем возможные варианты р₂, перебираем их и находим подходящие числа!

Показать ответ и решение

Ясно, что $n= 1$ подходит, ведь произведение из условия будет равно $1 =n3.$ Рассмотрим теперь $n> 1.$ Обозначим произведение его делителей буквой $P.$

Если число $n$ не является точным квадратом, то его делители можно разбить на $s$ пар с произведением $n$ в каждой (если число $n$ делится нацело на $√ - k < n$ , то оно делится нацело и на $n n-- √- m = k > √n = n$ ). Например, $18 =1 ⋅18= 2⋅9= 3⋅6$ . Так что делители бьются на пары с произведением $n$ в каждой, откуда $s P =n .$

По условию $3 P =n$ , тогда $s= 3.$ Число должно иметь $6$ делителей.

Если число является точным квадратом, то есть ещё делитель $√- n,$ поэтому $s+1 3 P = n 2 = n$ — противоречие с тем, что $s$ — целое число пар.

Для $k k n =p11⋅...ptt ,ki ∈ℕ$ количество различных делителей равно $t (1+ k1)...(1+ kt)≥ 2$ (берём каждое простое в каждой степени, считая нулевую). Если число $n$ должно иметь ровно $6$ делителей, то $6≥ 2t =⇒ t= 1 или t =2$ .

При $t= 1$ получаем $n= p5$ . Среди чисел от $1$ до $100$ подходит только $n =32.$

При $t= 2$ получаем $n= p1p22.$ Из условия на промежуток

$p22 ≤ 1020= 50 ⇐⇒ p2 ≤7 ⇐ ⇒ p2 ∈ {2,3,5,7}$ .

Добавим также условие $p22 ≥ 4 =⇒ p1 ≤ 25$ , затем остаётся просто перебрать по очереди все $p2$ , а затем выбрать подходящие простые $p1 ≤ 25$ , получим числа

22⋅3 =12,22 ⋅5 =20,22 ⋅7 =28,22⋅11 =44,22 ⋅13= 52,22⋅17= 68,22⋅19= 76,22⋅23= 92

32⋅2= 18,32⋅5= 45,32⋅7= 63,32⋅11= 99

52⋅2=50,52⋅3= 75

72⋅2= 98

Ответ:

$1,12,18,20,28,32,44,45,50,52,63,68,75,76,92,98,99$

Ошибка.
Попробуйте повторить позже

Задача 219#71294Максимум баллов за задание: 7

Натуральное число $n$ назовём почти квадратом, если $n$ можно представить в виде $n =ab,$ где $a$ и $b$ — натуральные числа, причем $a ≤b≤ 1,01a.$ Докажите, что для бесконечно многих натуральных $m$ среди чисел $m,m + 1,m + 2,...,m + 198$ нет почти квадратов.

Источники: СпбОШ - 2017, задача 11.4(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Если покрутить конструкцию на конкретных числах, то на уровне общих соображений, то всё становится достаточно понятно: "почти квадраты" лежат очень близко к квадратам (мы можем оценить это с помощью неравенств) и ясно, что с увеличением а у нас будут увеличиваться промежутки, на которых искомых чисел лежать не может. Но как же собрать это в строгое доказательство?

Подсказка 2

Попробуем пойти от противного. Какое утверждение обратно к нашему?

Подсказка 3

Разобьём натуральный ряд на отрезки по 199 чисел. Обратным к искомому будет утверждение о том, что во всех таких отрезках, кроме конечного количества с, будет содержаться "почти квадрат".
Сколько "почти квадратов" будет среди чисел от 1 до n²?

Подсказка 4

Получим оценку с двух сторон: оценка снизу связана с с, а оценку сверху построим из того, что b натурально и лежит в определённом промежутке. Осталось посмотреть, выполнима ли эта оценка при достаточно больших n.

Показать доказательство

Предположим противное. Разобьем натуральный ряд на отрезки по $199$ чисел. Тогда во всех отрезках, кроме, быть может, конечного количества $c,$ имеется почти квадрат. Отсюда следует, что среди чисел от $1$ до $2 n$ количество почти квадратов не меньше чем $n2- 199 − c,$ где $c$ — некоторая константа. С другой стороны, каждый такой почти квадрат имеет вид $ab,$ где $a≤n,$ $[ a-] b∈ a,a + 100 ,$ поэтому их количество не больше чем

n∑ ( ) 2 a100-+1 = n + n(n2+001)< n199 − c a=1

при достаточно большом $n.$ Противоречие.

Ошибка.
Попробуйте повторить позже

Задача 220#72730Максимум баллов за задание: 7

Известно, что $a,$ $b$ и $c$ — натуральные числа,

НО К(a,b)= 945 НО К(b,c)=525

Чему может равняться $НОК(a,c)?$ Введите все возможные варианты в порядке возрастания через пробел.

Источники: ШВБ-2017, отборочный тур

Подсказки к задаче

Подсказка 1

Попробуйте сначала разложить на простые множители числа, которым равны НОК(a,b) и НОК(b,c). Какое разложение могли бы иметь числа a, b, c?

Подсказка 2

НОК(a,b) = 3^3 * 5 * 7, НОК(b,c) = 3 * 5^2 * 7. Тогда a делится на 3^3. А что можно сказать про c? На какие числа делится НОК(a,c)?

Подсказка 3

НОК(a,c) делится на 3^3 * 5^2. Заметим, что НОК(a,b,c) делится на все 3 числа: НОК(a,b), НОК(b,c), НОК(a,c). Тогда НОК(a,b,c) делится 3^3 * 5^2 * 7. Каким тогда может быть НОК(a,c)?

Показать ответ и решение

Разложим числа на простые множители, так как $33$ встречается только в $HOK (a,b),$ следовательно $a..33, .$ аналогично получаем, что $.. 2 c.5$