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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Натуральные числа $a,b$ и $c,$ где $c≥2,$ таковы, что $1+ 1 = 1. a b c$ Докажите, что хотя бы одно из чисел $a+c, b+ c$ – составное.

Источники: Всеросс., 2013, РЭ, 10.6(см. olympiads.mccme.ru)

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

Подсказка 1:

Попробуйте, например, записать условие, что a + c составное, в другом формате, с которым проще работать.

Подсказка 2:

Если a + c составное, то НОД a и c больше 1 (почему?).

Подсказка 3:

Попробуйте преобразовать равенство из условия и подумайте, как к нему применить тот вывод про НОДы.

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

Достаточно показать, что хотя бы одно из двух чисел $d = (a,c) a$ и $d = (b,c) b$ больше $1.$ Действительно, если, например, $d > 1, a$ то $a+ c$ делится на $da$ и $a+c >$ $da,$ значит, $a+ c$ – составное число. Из условия следует, что $c(a +b)= ab;$ значит, $ab$ делится на $c.$ Но тогда, если $da = db =1,$ то и $c= 1,$ что противоречит условию.

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

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

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

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

На доске в строчку написано $n$ подряд идущих натуральных чисел в порядке возрастания. Под каждым из этих чисел написан его делитель, меньший этого числа и больший $1.$ Оказалось, что эти делители тоже образуют строчку подряд идущих натуральных чисел в порядке возрастания. Докажите, что каждое из исходных больше, чем $nk p1p2...pk-,$ где $p1,$ $p2,...,pk$ — все простые числа, меньшие $n.$

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

Подсказка 1

Попробуйте выделить некоторый инвариант для всех пар (a, b) чисел верхней строчке и числа под ним.

Подсказка 2

Для всех пар разность a-b фиксирована. Пусть она равна c. Что можно сказать про с?

Подсказка 3

Для любой пары (a, b) число c делится на НОД(a, b). Как можно оценить снизу значение c?

Подсказка 4

В нижней строчке встречается по крайней мере одно число, которое кратно числу k при всех k <= n. Как эти рассуждения можно связать с простыми числами меньшими n?

Подсказка 5

Число c делится на наибольшую не превосходящую n степень любого простого числа p, меньшего n, а, значит, и на произведение этих степеней по всем таким p. Как это помогает получить искомую оценку?

Подсказка 6

Пусть p^s — наибольшая степень p, не превосходящая n, тогда любое из исходных чисел не меньше чем, с > p^s > n/p для любого p.

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

Заметим, что все разности между числами и записанными под ними их делителями равны одному и тому же числу $c.$ Пусть $p$ — простое число, меньшее $n,$ а $s p$ — наибольшая его степень, не превосходящая $n.$ Тогда среди чисел во второй строке найдется делящееся на $s p.$ Но тогда на $s p$ делится и записанное над ним число в первой строке, а, значит, и число $c.$ Таким образом, число $c$ делится на наибольшую не превосходящую $n$ степень любого простого числа $p,$ меньшего $n,$ а, значит, и на произведение этих степеней по всем таким $p.$ Осталось заметить, что $s p > n∕p$ и любое число в исходной строке больше $c.$

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

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

Какое количество натуральных чисел $a$ обладает следующим свойством: “Наименьшее общее кратное чисел $16$ , $50$ и $a$ равняется $1200$ ”?

Источники: Физтех-2012, 11.8 (см. olymp.mipt.ru)

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

Подсказка 1

Разложите числа на простые множители и вспомните, как представляется НОК через эти множители.

Подсказка 2

Верно, он содержит в себе все самые большие степени вхождения простых множителей. Какие множители ОБЯЗАНО иметь число а, а какие МОЖЕТ? Когда это узнаем, то поймем, что для любого простого р1 мы можем взять все степени простого р2, правило умножения :)

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

2 4 4 2 1200= 5 ⋅2 ⋅3,16= 2,50= 2⋅5

Если $НОК (24,2⋅52,a)= 52 ⋅24⋅3$ , то в числе $a$ может быть любая степень двойки от $0$ до $4$ , любая степень пятёрки от $0$ до $2$ , обязательно первая степень тройки для того, чтобы она появилась в $НО К$ и больше никаких простых чисел, так как их нет в числе $1200.$

Всего получается $5⋅3⋅1= 15$ вариантов составления числа из множителей.

Ответ:

$15$

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

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

Для натурального $n$ обозначим $S =1!+ 2!+ ...+ n!. n$ Докажите, что при некотором $n$ у числа $S n$ есть простой делитель, больший $2012 10 .$

Источники: Всеросс., 2012, ЗЭ, 11.8(см. olympiads.mccme.ru)

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

Для простого $p$ и натурального $n$ обозначим через $v (n) p$ степень, в которой $p$ входит в разложение $n$ на простые множители. Заметим, что если $vp(n)⁄= vp(k)$ , то $vp(n ±k)= min(vp(n),vp(k)).$

Предположим противное, обозначим $2012 P = 10 .$ Тогда все простые делители чисел вида $Sn$ не превосходят $P.$

______________________________________________________________________________________________________________________________________________________

Лемма: Пусть $vp(Sn)< vp((n+ 1)!)$ при некотором $n.$ Тогда $vp(Sk) =vp(Sn)$ при всех $k≥ n.$

Доказательство: Обозначим $a= vp(Sn),b=vp((n +1)!),$ тогда $b ≥a+ 1.$ Заметим, что если $Sk = Sn+ (n+ 1)!+...+k!.$ В этой сумме все слагаемые, кроме первого, делятся на $a+1 p .$ а первое делится лишь на $a p .$ но не на $a+1 p .$ Значит и $Sk$ делится на $a p ,$ но не на $a+1 p .$

______________________________________________________________________________________________________________________________________________________

Рассмотрим некоторое простое $p≤ P.$ Ввиду леммы, если $vp(Sn)< vp((n+ 1)!)$ при некотором $n,$ то существует число $ap$ такое, что $vp(Sn) ≤ap$ при всех натуральных $n.$ Назовём такое простое число $p$ маленьким, все остальные простые числа, меньшие $P,$ назовём большими. Так как маленьких простых конечное количество, существует натуральное $M,$ большее любого числа вида $pap,$ где $p$ — маленькое.

Пусть теперь $p$ — большое простое число, а $n$ — такое число, что $p|n+ 2.$ Тогда из леммы имеем $vp(Sn+1)≥ vp((n +2)!)> vp((n+ 1)!),$ а это означает, что $vp(Sn)= vp(Sn+1− (n +1)!)= vp((n+ 1)!)=vp(n!).$ Последний переход верен, так как $n+ 1$ не кратно $p.$

Рассмотрим теперь $N = M ⋅P!− 2.$ По доказанному, $vp(SN)= vp(N!)$ для любого большого простого $p.$ Кроме того, поскольку $N ≥ M,$ то $vp(SN)≤ vp(pap)≤vp(N!)$ для любого маленького простого $p.$ Поскольку все простые делители числа $SN$ — либо большие, либо маленькие, отсюда следует, что $SN ≤ N!,$ что, очевидно, неверно. Противоречие.

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

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

Собственным делителем числа называется любой его натуральный делитель, кроме $1$ и самого числа. С составным натуральным числом $a$ разрешается проделывать следующие операции: разделить на наименьший собственный делитель или прибавить любое натуральное число, делящееся на его наибольший собственный делитель. Если число получилось простым, то с ним ничего нельзя делать. Верно ли, что с помощью таких операций из любого составного числа можно получить число $2011?$

Источники: Олимпиада Эйлера - 2012

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

Покажем, что наибольший простой делитель числа при указанных операциях не уменьшается, и потому мы никогда не получим число $2011$ из составного числа, имеющего простой делитель, больший чем $2011.$

Заметим, что наибольший собственный делитель составного числа $a$ делится на наибольший простой делитель $p$ этого числа. В самом деле, очевидно, что $a =qp,$ где $q$ — наименьший собственный (и наименьший собственный) делитель числа $a,$ и, поскольку $b>1,$ множитель $p$ должен остаться в разложении. В частности, если $p= q,$ то это всё равно верно, поскольку тогда $a= pn,$ где $n >1.$

Поэтому если мы делим составное число на $q,$ то получаем частное $b= a∕q,$ где $q$ — наименьший собственный делитель $a,$ и множитель $p$ остаётся в разложении числа $b.$

Если же мы к числу $a= bq$ прибавляем кратное $b$ его наименьшему собственному делителю $q,$ то получаем число $b(q+c),$ у которого наибольший простой делитель не меньше, чем наибольший простой делитель числа $b,$ то есть не меньше $p.$

Ответ:

неверно

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

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

Даны натуральные числа $a$ и $b$ , причём $a <1000$ . Докажите, что если $a21$ делится на $b10$ , то $a2$ делится на $b.$

Источники: Олимпиада Эйлера, 2010, РЭ, 4 задача(см. old.mccme.ru)

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

Рассмотрим некоторое простое число $p$ , пусть оно входит в число $a$ в степени $k a$ , в число $b$ — в степени $k b$ . Тогда из условия мы имеем, что $21ka ≥10kb$ , а нам требуется показать, что $2ka ≥ kb$ . Пусть это неверно. Тогда $2ka < kb ⇐⇒ 20ka < 10kb ≤21ka$ . Заметим, что первые два числа в неравенстве кратны десяти, поэтому $10kb ≥ 20ka+ 10$ , то есть $21ka ≥ 20ka+ 10 ⇐⇒ ka ≥10$ . Но может ли в число, меньшее $1000$ , какое-то простое число входить в хотя бы десятой степени? Нет, поскольку даже минимальное простое $10 2 > 1024$ этому условию не удовлетворяет. Мы получили противоречие, значит, требуемое доказано.

Ответ:

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

Курсы

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

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

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

Какие значения может принимать наибольший общий делитель натуральных чисел $m$ и $n,$ если при увеличении числа $m$ на $6$ он увеличивается в $4$ раза?

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

Подсказка 1

Ага, нам в условии даны НОДы, значит, нужно смотреть на делители чисел, для которых мы знаем НОД. Обратите внимание, что m делится на d, а m + 6 делятся на 4d. Подумайте, как с помощью этого мы можем оценить d.

Подсказка 2

m и m + 6 делятся на d, следовательно, их разность тоже делится на d. Какие значения может принимать d?

Подсказка 3

Не забудем про то, что m + 6 и n делятся на 4, значит, m и n – четные. Что тогда можно сказать про d?

Подсказка 4

d – четное натуральное число, которое является делителем числа 6. Осталось найти пример на d = 2 и d = 6.

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

Пусть

Н ОД(m,n)= d, НОД (m + 6,n)= 4d

Значит, на число $d$ делятся числа $m + 6,m,$ а следовательно и их разность $m +6− m = 6.$ Поэтому возможны лишь следующие случаи: $d =1,d= 2,d =3,d= 6.$

Так как числа $m +6,n$ делятся на $4,$ то числа $m$ и $n$ — четные, значит, число $d$ тоже чётное. Следовательно, $d =2$ или $d= 6.$ Привидём примеры для этих двух случаев.

При $d= 2$ должно быть

НОД (m,n)= 2, Н ОД(m+ 6,n)=8

Этим условиям удовлетворяет, например, пара $n =8,m =10.$

При $d= 6$ должно быть

Н ОД(m,n)= 6, НОД (m + 6,n)= 24

Этим условиям удовлетворяет, например, пара $n =24,m =18.$

Ответ: 2 и 6

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

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

Найдите наименьшее натуральное $n,$ для которого число $nn$ не является делителем числа $2008!$

Источники: ММО-2008, 11.2(см. mmo.mccme.ru)

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

Подсказка 1

Можно ли ограничить n снизу, пользуясь определённой его степенью?

Подсказка 2

Заметим, что если n² ≤ 2008, то 2008! делится на nⁿ. Попробуйте оценить число 2008 через квадраты.

Подсказка 3

44² < 2008 < 45², какие n тогда можно рассматривать?

Подсказка 4

Нам будет достаточно проверять делимость 2008! на nⁿ при n > 45.

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

Если $n2 ≤2008,$ то $2008!$ делится на $nn$ (так как числа $n,2n,...,(n − 1)n$ и $n2$ содержатся среди чисел $1,2,...,2007,2008$ ). Так как $2 2 44 < 2008 <45 ,$ то достаточно проверить делимость $2008!$ на $n n$ при $n >45.$

Ясно, что $2008!$ делится на $45 45 90 45 =5 ⋅3 ,$ так как среди чисел $1,2,...,2007,2008$ заведомо найдётся $45$ чисел, кратных $5,$ и $90$ чисел, кратных $3$ ( $5⋅45= 22< 2008$ и $3⋅90= 270<2008$ ).

$2008!$ делится на $46 46 46 46 = 2 23 ,$ так как среди чисел $1,2,...,2007,2008$ заведомо найдётся $46$ чётных чисел и $46$ чисел, кратных $23$ ( $23⋅46= 1058< 2008$ ).

$2008!$ не делится на $47 47 ,$ так как число $47$ простое, и поэтому среди чисел $1,2,...,2007,2008$ есть лишь $42$ числа, кратных $47$ ( $47⋅42 =1974< 2008 <2021= 43 ⋅47$ ).

Ответ:

$47$

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

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

Натуральные числа $a$ , $b$ и $c$ таковы, что $НО К(a,b)= 90$ и $НОК(a,c)= 120$ . Найдите $НОК(b,c)$ .

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

Подсказка 1

Сразу же раскладываем результат НОКов на степени простых чисел, потому что именно они влияют на НОК, заметьте, что НОК от двух чисел обязательно говорит о том, что какая-то степень простого точно содержится хотя бы в одном из двух чисел, а ещё, что "a" участвует аж в двух известных нам произведениях, может стоит вести рассуждения про него?

Подсказка 2

Посмотрите, на то, что в одном НОКе есть простое число в большей степени, чем в другом, в каком тогда числе оно содержится?

Подсказка 3

Точно не в "a", потому что иначе оба НОКа содержали бы его, так мы понимаем, что именно "b" делится на 3², подумайте, а в каком числе содержится 2³?

Подсказка 4

Верно, в "c", а что мы можем сказать про 5? До этого мы получали необходимые условия, которые как-то фиксировали наши выражения, если же мы не сможем найти новые условия, то может стоит найти примеры, которые подтверждают то, что наши случаи возможны, а если перебрать все такие, то наша задача станет решена!

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

Разложим все НОКи:

2 3 НОК(a,b)= 90= 2⋅3 ⋅5,НО К(a,c)= 120 =2 ⋅3⋅5.

Тогда из первого НОКа мы понимаем, что $a$ или $b$ содержит в своем разложении $32$ . Если $a$ кратно $32$ , то $НОК (a,c)=120$ должен быть тоже кратен $32$ , но это не так. Тогда именно $b$ содержит в своем разложении $32$ .

Аналогично поймем, что $23$ входит в разложение $c$ .

Теперь мы уже знаем, что $НО К(b,c)$ содержит $32$ и $23$ . $НО К(b,c)$ может содержать еще 5 (именно в первой степени).

Приведем примеры для $НОК (b,c) =23⋅32 = 72$ и $НОК (b,c)= 23⋅32⋅5= 360$ :

2 3 1)a= 5,b =2⋅3 ,c=2 ⋅3,

2 3 2)a= 1,b =2⋅3 ⋅5,c=2 ⋅3⋅5.

Ответ: 72 или 360

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

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

Чему может быть равно произведение нескольких различных простых чисел, если оно кратно каждому из них, уменьшенному на $1?$ Найдите все возможные значения.

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

Подсказка 1!

1) Давайте попробуем восстанавливать наши множители с самого начала. Важное свойство почти всех простых чисел - нечетность. Значит перемножение будет делиться на двойку!

Подсказка 2!

2) Итак, поняли, что одно из простых чисел это 2. Попробуем понять, что тогда может быть следующим по возрастанию множителем в числе. Пусть это p2. Тогда раз наше число делится на p2-1, чему может быть равно p2?

Подсказка 3!

3) Верно, p2-1 может быть только двойкой, тогда p2 это 3! Теперь попробуйте таким же раскручиванием цепочки довести ее до конца, до момента, когда все множители, которые могут получиться, будут составными!

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

Хотя бы одно из простых чисел нечётно, потому число кратно двум. Пусть это $N =p ⋅...⋅p ,p <p ,i∈ {1,...k− 1}, 1 k i i+1$ где $p =2. 1$ Далее будем находить числа по порядку

Число содержит $p2,$ делителем $p2− 1$ может быть только $2,$ поскольку остальные делители больше $p2− 1,$ откуда оно равно $2$ и $p2 = 3.$ Подойдёт $N = 6,$ пойдём дальше.

Число содержит $p3,$ делителями $p3− 1$ могут быть только $p1,p2,$ но оба они меньше $p3− 1,$ потому $p1⋅p2 = 6 ⇐⇒ p3 =7.$ Подойдёт $N =2 ⋅3 ⋅7 =42.$

Число содержит $p4,p4 − 1$ может быть равно только $p1p3 = 14,p1p2p3 = 42,$ поскольку $p1p2 <p3.$ В первом случае $15= 14+ 1$ составное, во втором $p4 = 43$ и подходит $N = 2⋅3⋅7⋅43 =1806.$

Пусть теперь число содержит $p5,$ отсюда $p5 − 1$ равно одному из чисел $p1p4 =86,p1p2p4 = 258,p1p3p4 = 602,p1p2p3p4 = 1806,$ где все числа, увеличенные на один, будут составными, откуда больше четырёх простых чисел быть не может.

Ответ:

$6,42,1806$

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

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

Натуральные числа $b$ и $n,$ большие 1, таковы, что для каждого натурального $k > 1$ существует натуральное число $a k$ такое, что $b− an k$ делится на $k.$ Докажите, что $n b =A$ для некоторого натурального $A.$

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

Пусть $b= pα1...pαs, 1 s$ где $p i$ — различные простые числа. Тогда нам нужно показать, что все $α i$ делятся на $n.$ Рассмотрим $k= b2.$ Тогда $n b− ak$ делится на $2 b,$ в частности, на каждое $2αi pi ,$ что больше, чем $αi pi .$ Тогда

n αi ak ≡ b≡ 0 (mod pi )

n αi+1 ak ≡b⁄≡ 0 (mod pi )

Значит, степень вхождения $pi$ в $αn k$ — это в точности $αi,$ но эта степень делится на $n,$ что и требовалось доказать.

Интенсивы

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

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

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

К натуральному числу $a> 1$ приписали это же число и получили число $b,$ кратное $a2.$ Найдите все возможные значения числа $-b a2.$

Источники: Турнир городов - 2004, весенний тур, базовый вариант, 11.2

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

Подсказка 1

Когда в задаче идет речь о «приписывании» цифр, полезно оценить исходное число через степени десятки.

Подсказка 2

b/a² =(10ⁿ+1)a/a²=(10ⁿ+1)/a. Зная, что а - n-значно, как можно оценить дробь (10ⁿ+1)/a?

Подсказка 3

Подумайте, на что может делиться 10ⁿ+1.

Подсказка 4

10ⁿ+1 нечётно, сумма цифр числа равна 2, и на 5 оно тоже не делится, что осталось?

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

Если число $a$ $n$ -значно, то $b =(10n+1)a.$ Отсюда

-b (10n+-1)a 10n+-1 a2 = a2 = a

Ясно, что $n−1 a ⁄=10$ (в таком случае $b$ не кратно $2 a$ ), значит,

10n+ 1 1< ---a--< 10

Число $10n +1$ (а тем более, частное) не делится ни на $2,$ ни на $3$ (сумма цифр равна $2$ ), ни на $5,$ поэтому единственное возможное частное – $7.$ Такое частное можно получить например, при $3 n = 3, a= 143= 107+1.$

Ответ:

$7$

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

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

Существует ли такое натуральное число, что произведение всех его натуральных делителей (включая $1$ и само число) оканчивается ровно на $2001$ ноль?

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

Лемма. Для любого натурального числа $n$ произведение всех его делителей равно $nd(n)∕2,$ где $d(n)$ — число делителей числа $n.$

Докажем лемму. Пусть делители числа $n$ равны $d1,$ $d2,$ …, $dd(n).$ Их можно разбить на пары вида $n- (di,di),$ произведение каждой пары равно $n.$ В случае, когда $n$ не точный квадарт таких пар $d(n)∕2,$ поэтому общее произведение всех делителей равно $d(n)∕2 n .$ В случае когда $n$ — полный квадрат, $√- n$ останется без пары, но так как $d(n)∕2$ будет полуцелым, то формула тоже будет верна.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь применим лемму. Возьмём $2000 n= 5⋅2 .$ Тогда пятёрка входит в произведение всех делителей в $2001$ степени, а двойка в $2001⋅2000$ степени.

Следовательно, минимальная из степеней вхождения равна $2001,$ значит произведение всех делителей оканчивается ровно на $2001$ ноль.

Ответ:

существует

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

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

Докажите, что каждое натуральное число является разностью двух натуральных чисел, имеющих одинаковое количество простых делителей. (Каждый простой делитель учитывается один раз, например, число $12$ имеет два простых делителя: $2$ и $3.$ )

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

Подсказка 1

Пусть дано число n. Попробуйте построить пример отдельно для чётного и для нечётного n. Случай чётного числа заметно проще, начните с него.

Подсказка 2

Для нечетного n попробуйте построить пример, где оба числа будут кратны n. Пусть это будут числа k·n и (k+1)·n. Если коэффициенты k и k+1 — последовательные числа, то как тогда может быть устроено количество их простых делителей?

Подсказка 3

Один из коэффициентов k и k+1 обязательно делится на 2. Попробуйте сделать один коэффициент простым, а второй таким, чтобы в его разложение добавилась только двойка. Как это можно устроить?

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

Если число $n$ чётно, то есть $n= 2m,$ то искомыми числами будут $4m$ и $2m.$ Пусть $n$ нечётно, $p ,...,p 1 s$ — его простые делители и $p$ — наименьшее нечётное простое число, не входящее во множество $p1,...,ps.$ Тогда искомыми будут числа $p⋅n$ и $(p− 1)⋅n,$ так как, в силу выбора $p,$ число $p− 1$ имеет своими делителями число $2,$ и, возможно, какие-то из чисел $p1,...,ps.$

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

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

Найдите все пары целых чисел $(x,y),$ для которых числа $x3 +y$ и $x+ y3$ делятся на $x2+ y2.$

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

Подсказка 1:

Попробуйте обозначить НОД x и y через d и что-то про него понять.

Подсказка 2:

Итак, у вас должно было получиться, что x и y взаимно просты. Теперь давайте осознаем, что любая линейная комбинация чисел x³ + y и x² + y² или x + y³ и x² + y² будет делиться на x² + y². Попробуйте взять какую-нибудь удобным комбинацию, которая даст интересную делимость.

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

Пусть $d =$ НОД $(x,y).$ Тогда $x= du, y = dv,$ где $u$ и $v$ взаимно просты. По условию $d3u3+ dv$ делится на $d2,$ поэтому $v$ делится на $d.$ Аналогично $u$ делится на $d.$ Значит, $d= 1,$ то есть $x$ и $y$ взаимно просты. Тогда и число $2 2 x + y$ взаимно просто с $y.$ Число $( 2 2) (3 ) x x +y − x +y = y(xy − 1)$ делится на $2 2 x + y.$ Поскольку $2 2 x + y$ и $y$ взаимно просты, то $xy− 1$ делится на $2 2 x + y .$ Но это возможно только при $|xy|≤ 1.$ Действительно, в противном случае $2 2 0 <|xy− 1|< 2|xy|≤x + y .$ Непосредственная проверка всех оставшихся вариантов $(x,y =0,±1)$ дает восемь решений $(±1,±1),(0,±1),(±1,0).$

Ответ:

$(1,1), (1,0), (1,−1), (0,1), (0,−1), (−1,1), (−1,0), (−1,−1)$

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

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

Найдите все натуральные $n,$ у которых ровно $16$ делителей

1 =d1 < d2 < ...< d16 = n

причем $d6 =18,$ а $d9− d8 = 17.$

Источники: Irish-1998, Andreescu p.127

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

Посмотрим внимательно на $d = 18. 6$ Если $n$ делится на $d , 6$ то у $n$ есть те же делители, что и у $18,$ то есть у $n$ есть делители $2,3,6,9.$ По условию $d1 = 1,d6 = 18,$ следовательно, делители $d2,d3,...,d5$ это в точности делители $18.$

Тогда число $n$ может быть представимо в следующих видах: (a) $1+α 2+β n= 2 ⋅3 .$ В этом cлучае общее количество делителей это

(1+ 1+α)(3+β)= 16

То есть или $α= 2,β = 1$ или $α = 0,β =5.$ Но первый случай невозможен, так как появился бы делитель $4.$ Рассмотрим второй случай. Если $n = 2⋅37,$ то $d =52,d =81, 8 9$ что противоречит условию $d − d = 19. 9 8$

(b) $1+α 2+β k n= 2 ⋅3 ⋅p ,$ где $p$ — какой-то простой делитель, больше $18.$ В этом cлучае общее количество делителей это

(1+ 1+ α)(3+ β)(1+ k)= 16

То есть $α= 0,β = 1,k= 1$ и только такой случай, так как $3+β ≥3.$ Переберем случаи, где может быть $p.$

Если $p$ больше $d = 18, 6$ но меньше $d = 27, 8$ то $d =p 7$ и $d = 2p, 9$ откуда $d − d = 2p− 27= 17, 9 8$ откуда $p=22,$ что невозможно.

Если $p$ больше $d7 = 27,$ но меньше $d9 = 54,$ то $d9− d8 = 54− p =17,$ откуда $p= 37.$

Если $p$ больше $d8 = 54,$ то $d9 =p.$ Тогда $d9− d8 = p− 54 =17,$ откуда $p= 71.$

Получаем $2$ ответа: $3 n= 2⋅3 ⋅37$ или $3 n= 2⋅3 ⋅71.$

Ответ:

$2⋅33⋅37,2 ⋅33⋅71$

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

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

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

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

Найдите все наборы из $100$ чисел таких, что сумма четвёртых степеней любых четырёх чисел делится на их произведение.

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

Подсказка 1

Пусть a — НОД всех чисел из набора. Рассмотрите любые 4 элемента этого набора и обозначьте их за ax, ay, az, at. Попробуйте записать условие на эти числа...Ого! Да ведь a сократилось и набор x, y, z, t тоже подходит под условие задачи.

Подсказка 2

Подумайте какое простое число может быть делителем элементов множества.

Подсказка 3

И правда, нетрудно получить, что единственный простой делитель элементов множества — 3. Также можно оценить степень вхождения 3 в элементы набора. В конце не забудьте сделать проверку!

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

Пусть ${a }100 ii=1$ — один из искомых набров. Пусть $α = НОД{a }100> 1. ii=1$ Тогда для любых четырех элементов $αx,αy,αz,αt$ верно

4 4 4 4 4 α xyzt | (αx)+ (αy)+ (αz) + (αt)

что равносильно

4 4 4 4 xyzt | x +y + z + t

таким образом набор ${ai}1i0=01 α$ так же удовлетворяет условию. Тем самым, мы показали, что достаточно найти лишь те наборы, НОД всех элементов которого равен $1.$

Пусть $НОД{ai}100= 1 i=1$ и нашлись два не взаимно простых элемента набора $x$ и $y,$ пусть $s$ — некоторый общий простой делитель. Пусть $p,q,r$ — некоторые элементы набора. Тогда

4 4 4 4 s | x + y + p +q

s | x4+ r4+ p4 +q4

вычитая, получим, что $s | r.$ В силу произвольности выбора $r,$ мы можем показать, что каждый элемент набора кратен $p,$ что влечет противоречие, таким образом, все элементы набора попарно взаимно просты.

Пусть в наборе присутствует число $x,$ в разложении которого присутствует простой делитель $p⁄= 3.$ Тогда для любых элементов $a,b,u,v,l$ набора верно, что

4 4 4 4 p | x + a + b +u

4 4 4 4 p | x +a + b +v

p | x4+a4+ b4+l4

следовательно, $u4 ≡ v4 ≡ l4(modp),$ кроме этого

p |x4 +u4+ v4+ l4

следовательно,

p | x4 +3u4

в силу $p⁄= 3,$ получили противоречие.

Таким образом, единственным простым делителем элементов множества может является $3,$ несложно показать, что степень вхождения $3$ в элемент набора, отличный от $1,$ равна $1.$ Прямой проверкой убедимся, что множества ${1}10i=01,{3,{1}99i=1}$ являются подходящими.

Ответ:

${α}100 i=1$ или ${3α,{α}99 } i=1$ для любого натурального $α$

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

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

Найдите все натуральные числа, имеющие ровно шесть делителей, сумма которых равна $3500.$

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

Подсказка 1

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

Подсказка 2

Попробуйте оценками сузить перебор. Какие разложения заведомо не подходят?

Подсказка 3

В итоге остаётся случай (1+p+p²)(1+q) = 3500. Здесь поможет разложение числа 3500 на простые множители. Попробуйте поработать сначала с первой скобкой и понять, чему она может быть равна.

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

Запишем каноническое разложение натурального числа $n = pα1 ⋅pα2⋅...⋅pαk. 1 2 k$ Его количество делителей равно $(α + 1)(α + 1)...(α +1). 1 2 k$ Если это число равно $6,$ то либо $k= 1$ и $α1 = 5,$ либо $k= 2,α1 = 2,α2 = 1.$ То есть либо $5 n= p,$ либо $2 n = pq$ ( $p$ и $q$ — простые).

В первом случае $2 3 4 5 1 +p+ p + p +p + p = 3500,$ откуда $2 3 4 p(p+ p +p + p )=3499.$ Число $3499$ не делится на $2,3,5$ и $7,$ поэтому $p> 10,$ но в этом случае $2 3 4 p(p+ p +p + p )>3499.$ Поэтому это уравнение решений в простых числах не имеет.

Во втором случае $2 2 1+ p+ p +q +pq+ pq =3500,$ то есть $2 3 (1+ p+ p)(1+q)= 5 ⋅7⋅4.$ Первый множитель нечётен и не кратен $5$ (чтобы убедиться в этом, достаточно это утверждение проверить для соответствующих остатков). Отсюда, учитывая, что $2 1 +p+ p > 1,$ имеем $2 1+ p+p = 7.$ Значит, $p= 2,$ $q = 499.$ Числа $2$ и $499$ — простые. Искомое число $n =22⋅499= 1996.$

Ответ:

$1996$

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

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

Последовательность натуральных чисел $a i$ такова, что

НОД(ai,aj)=H ОД(i,j)

для всех $i⁄= j.$ Докажите, что $a = i i$ для всех $i∈ ℕ.$

Источники: Всеросс., 1995, ЗЭ, 10.5(см. math.ru)

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

Подсказка 1:

Глобально в этой задаче нужно просто поиграться с НОДами. Попробуйте рассмотреть НОДы чисел с какими-то интересными индексами.

Подсказка 2:

Например, если рассмотреть НОД членов с индексами i, 2i, станет ясно, что aᵢ ≥ i.

Подсказка 3:

А теперь, предположив, что aᵢ > i, попробуйте рассмотреть НОД такой пары, который с одной стороны равен одному числу, а с другой стороны - другому.

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

Так как каждое $a i$ делится на НОД $(a,a )= i 2i$ НОД $(i,2i)= i$ , то $a ≥i i$ для всех $i∈ ℕ.$ Предположим, что $a >i i$ при некотором $i.$ Тогда, с одной стороны, НОД $(ai,aai) =$ НОД $(i,ai)= i$ (так как $ai$ делится на $i$ ), а с другой стороны, поскольку $aai$ делится на $ai,$ то НОД $(ai,aai)= ai > i.$ Противоречие.

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

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

Даны натуральные числа $a$ и $b$ такие, что число $a+-1+ b+-1 b a$ является целым. Докажите, что наибольший общий делитель чисел $a$ и $b$ не превосходит числа $√ ---- a+b.$

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

Подсказка 1:

Чтобы с суммой дробей было проще работать, её однозначно стоит преобразовать в дробь.

Подсказка 2:

Пусть НОД a и b равен d. В какой степени он входит в знаменатель дроби? Что можно сказать про числитель или его отдельные слагаемые?

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

Имеем:

a+-1 b+-1 a2+-b2+a-+b b + a = ab

Пусть $d$ — наибольший общий делитель чисел $a$ и $b.$ Так как $ab$ делится на $2 d ,$ то $2 2 a + b+ a+ b$ делится на $2 d.$ Число $2 2 a +b$ также делится на $2 d .$ Поэтому $a+b$ делится на $2 d$ и $√---- a +b≥ d.$

Следующая подтема