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

Оценочная теория чисел

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

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

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

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

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

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

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

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

Даны целое $a> 0,$ не являющееся целой степенью числа $10,$ и целое $b> 0.$ Верно ли, что существует такое целое $n >0,$ что в десятичной записи числа $n a$ встречается десятичная запись числа $b?$ Например, для $a= 2$ и $b= 19$ можно выбрать $n =13,$ т.к. $13 2 = 8192,$ в записи которого есть $19.$

Источники: Иннополис - 2025, 11.5 (см. lk-dovuz.innopolis.university)

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

Подсказки по 119891:

Подсказка 1:
Утверждение, про которое нас спрашивают, слишком общее. Давайте рассмотрим более частный вариант. Покажем, что найдётся число a^n, запись которого начинается с числа b.

Подсказка 2:

Иными словами, мы хотим подобрать такие целые положительные m и n, что 10^m • b < a^n < 10^m • (b + 1). Это сразу даст реализацию первой подсказки и решение задачи.

Подсказка 3:

В неравенстве довольно много степеней. Почему бы не прологарифмировать его по основанию 10?

Подсказка 4:

На самом деле это неравенство скрывает более общий факт. Запишем его так: lg(b) < nlg(a) - m < lg(b+1). Кстати, а мы же знаем, что a — не степень 10. Что можно сказать про число lg(a)?

Подсказка 5:

Докажите, что для иррационального x и любого интервала (u, v) найдутся целые положительные m, n такие, что u < nx - m < v.

Подсказка 6:

Попробуйте найти две пары чисел (m, n), чтобы разница между числом, соответствующим первой паре и числом, соответствующим второй паре, была меньше длины отрезка (u, v). Рассмотрите разницу t этих чисел, а также числа 2t, 3t, 4t, ..... Не найдётся ли среди них нужное?

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

Докажем, что для любого целого $a≥ 2$ ( $a⁄= 1= 100)$ и любого целого $b> 0$ найдется целое $n> 0,$ для которого десятичная запись числа $n a$ начинается с последовательно записанных цифр числа $b$ — иными словами, найдутся такие целые положительные $m,n,$ что

m n m 10 ⋅b< a < 10 ⋅(b+ 1)

Прологарифмируем последнее двойное неравенство с основанием $10:$

m + lgb <n ⋅lga< m +lg(b+ 1)

lgb< n⋅lga − m < lg(b+1)

Докажем, что $lga$ иррационально: если это не так, то $lga= pq$ для некоторых целых положительных взаимно простых $p,q,$ тогда $10p = aq,$ что невозможно. Итак, $lga$ иррационально.

Для завершения решения задачи можно доказать, что для любого иррационального $x> 0$ и любого выбранного интервала $(u,v)$ $(0< u< v)$ найдутся такие целые положительные $m,n,$ что

u< nx− m <v

Заметим, что для любого целого $n >0$ можно выбрать такое целое $mn > 0,$ что $0< nx− mn < 1.$ Пусть $k= ⌈v1−u⌉,$ т.е. отрезок $[0,1]$ можно разбить на $k$ равных отрезков, длина каждого из которых будет меньше длины интервала $(u,v).$ Рассмотрим бесконечный набор чисел $x− m1,$ $2x− m2,$ $3x− m3,...$ и выберем из него два числа попадающие в один и тот же из упомянутых $k$ отрезков — пусть это числа $ix− mi$ и $jx− mj$ (без ограничения общности будем считать, что первое меньше второго). Тогда

jx− m − (ix− m )= t∈(0;1∕k) j i

Для найденного $t$ рассмотрим числа $t,2t,3t,...$ — ввиду $t< 1∕k$ среди них найдется число, лежащее на интервале $(u,v),$ что и требовалось доказать.

Осталось заметить, что в условиях нашей задачи $x= lg a$ — иррациональное положительное число; $(u,v)=(lgb,lg(b+ 1))$ — положительный интервал (если $b= 1⇒ lgb= 0,$ то в качестве $u$ можно выбрать любое число из интервала $(0;lg(b+1))).$ Итак, найдутся такие целые положительные $m,n,$ что $lgb< n⋅lga− m < lg(b+ 1),$ т.е. десятичная запись числа $an$ будет начинаться с цифр числа $b.$

Ответ:

Да, верно

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

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

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

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

Натуральные числа $m > n$ таковы, что дробь $3m+2 3n+2$ есть целое число. Докажите, что $m> n2.$

Источники: Бельчонок - 2025, Вариант 4, 11.5(см. dovuz.sfu-kras.ru)

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

Подсказка 1

Доказать требуемое можно через довольно естественную идею. Давайте поделим m на n с остатком: m = qn + r и покажем, что q ≥ n.

Подсказка 2:

В контексте решения будет выгодно использовать сравнения по модулю 3ⁿ + 2. С их помощью можно упростить числитель.

Подсказка 3:

Если вы правильно применили сравнения, у вас должно возникнуть два случая — при чётном и нечётном q. В обоих случаях стоит представить условие с делимостью как равенство: числитель равен знаменателю, умноженному на некоторое целое. Далее попробуйте сделать какие-то грубые оценки. Например, если покажете, что 2ⁿ > 3^q, то очевидно n > q.

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

Разделим $m$ на $n$ с остатком: пусть $m = nq+ r,$ где $0≤ r< n$ и $q ≥ 1$ (так как $m > n).$ Заметим, что $3n ≡ −2 (mod 3n+2).$ Тогда имеем

m n q qr n 0≡ 3 + 2≡ (3 ) + 2≡(−2) 3 (mod 3 + 2)

Рассмотрим два случая: $q$ четно и $q$ нечетно.

Первый случай. Пусть $q$ четно. Тогда $2q3r+2 =k(3n+ 2).$ Для некоторого натурального $k.$ Тогда имеем $2≡ 2k (mod 3r),$ так как $r< n$ Следовательно, $k= 3rl+ 1$ для некоторого натурального $l.$ Значит, $2q3r+ 2= (3rl+1)(3n +2)$ (подставили $k$ в равенство), то есть $2q = 3nl+ 3n−r+2l> 3n,$ откуда следует, что $q > n.$ Но тогда $m = nq+r >n2,$ что и требовалось.

Второй случай. Пусть $q$ нечетно. Тогда $qr n 2 3 − 2 =k(3 +2),$ поскольку

qr n −2 3 +2 ≡0 (mod 3 + 2)

Так как $r< n,$ получаем $− 2≡ 2k (mod 3r).$ Следовательно, $k= 3rl− 1$ для некоторого натурального $l.$ Значит,

q r r n 2 3 − 2= (3 l− 1)(3 + 2)

то есть $2q = 3nl− 3n−r+ 2l.$ Если при этом $l≥2,$ то для того, чтобы выполнялось равенство, приведенное выше, необходимо, чтобы выполнялось неравенство $2q > 3n,$ так как в этом случае $3nl− 3n−r+2l> 3n⋅2− 3n = 3n.$ Тогда $q >n.$ Если же $l= 1$ ( $l∈ℕ,$ как следствие одного из приведенных выше равенств). Тогда и $r≥ 1.$ Действительно, в противном случае $r= 0$ и $2q = 3n− 3n +2 =2$ и $q =1.$ Но тогда $n < m= nq+ r= n⋅1+ 0= n$ — противоречие. Итак, $l= 1$ и $r≥ 1,$ тогда

q n n−r n n−1 n−1 n−1 n 2 = 3 − 3 +2 ≥3 − 3 + 2= 2⋅3 +2> 2⋅3 > 2

Итак, $q >n.$ Но тогда аналогичным образом, как в первом случае, можно получить, что $m > n2.$

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

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

Пусть $a = [√1]+[√2]+...+[√n]. n$ Докажите, что среди элементов последовательности $a,a ,... 1 2$ есть лишь конечное количество простых чисел, и найдите наибольшее из них.

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

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

Подсказка 1:

Пусть k — наибольше целое число такое, что k² ≤ n. Значит, n < (k+1)². Ясно, что [√n] = k. Вас это ни на что не наталкивает?

Подсказка 2:

А давайте представим n как k² + t. Но ведь мы же тогда можем вычислить n-й член, используя переменные k и t, потому что t+1 последних слагаемых равны k, следующие k² - (k-1)² слагаемых равны k-1 и так дальше.

Подсказка 3:

Осталось лишь внимательно посмотреть на выражение и заметить, что при k больших некоторого числа оно будет иметь определённый делитель.

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

Пусть $k$ — натуральное и $k2 ≤ n< (k +1)2.$ Тогда $[√n]= k.$ Значит, $[√n-]$ принимает фиксированное значение, равное $k,$ пока $n$ пробегает отрезок $2 2 [k ,(k +1) − 1],$ длина которого равна $2k+1.$ Значит, если $2 n = k +t,$ где $0≤ t≤2k,$ то

k∑−1 k∑−1 k∑−1 an = i(2i+ 1)+ k(t+1)= 2 i2+ i+k(t+1)= i=1 i=1 i=1

(k − 1)k(2k− 1) (k − 1)k (k − 1)k(4k+ 1) = -----3------+ --2---+ k(t+ 1)= -----6------+ k(t+ 1)

Заметим, что дробь $(k−1)k(4k+1) ----6----$ принимает целые значения при натуральных $k.$ Если множитель $k$ в числителе этой дроби не сокращается полностью со знаменателем, то данная дробь не взаимно проста с числом $k(t+1)$ (у них обоих есть общий делитель, входящий в $k$ и не сократившийся после деления на $6).$ Ясно, что при $k> 6$ такой множитель заведомо останется. Поэтому $k≤ 6$ и $n ≤72− 1= 48.$ Значит, при $n≥ 49$ все числа $an$ составные.

При $k= 6$ получаем формулу $an =125+ 6(t+ 1),$ где $t≤ 12.$ При $t= 12$ находим $a48 =203= 7⋅29,$ а при $t= 11$ получаем $a47 = 197$ — простое. Таким образом, наибольшее простое число в последовательности $an$ равно $197$ и соответствует индексу $n =47.$

Ответ:

$197$

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

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

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

-a2-+b2 b2-+c2- c2-+a2- c(a+ b) = a(b+ c) = b(c+ a).

Докажите, что $a= b= c.$

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

Первое решение. Выражение симметрично относительно $a,b,c,$ так что можно считать $a≥ b≥c.$ Тогда из натуральности получаем $2 2 2 2 a + b ≥b + c$ и $c(a+ b)≤ a(b+c).$ Из таких неравенств на числитель и знаменатель первых двух дробей получаем, что должны выполняться точные равенства. Значит, $2 2 2 2 a +b = b +c$ и $a= c,$ но $b$ между ними, так что $a= b= c,$ что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Пусть

a2+ b2 b2+ c2 c2+ a2 k= c(a+-b) = a(b+c) = b(c-+a).

Тогда имеем

k⋅c(a +b)= a2+b2

k⋅a(b +c)= b2+ c2.

Вычитая полученные равенства, получаем

kb(c− a)= (a − c)(a+ c).

Если $a⁄= c,$ то, сократив, получим равенство $kb= −a − c.$ С другой стороны, левая часть очевидно больше 0, а правая — меньше, откуда получаем противоречие. Значит, $a= c.$ Аналогично получаем $a =b$ и $b= c.$

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

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

Найдите все натуральные $n$ такие, что если $1 =d < d < ...< d < d =n 1 2 k k+1$ — все натуральные делители $n,$ то $n$ делится на $d + d 1 2$ и $d1+d2+ ...+ dk.$

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

Подсказка 1.

Сначала рассмотрим d₁+d₂. Нам известно, что d₁=1. Тогда d₂ и d₂+1 вместе являются делителями числа n. Какой вывод из этого можно сделать?

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

Заметим, что $d +...+ d > d , 1 k k$ так что эта сумма в точности равна $n.$ Так как $d + d = d +1, 1 2 2$ то есть у $n$ есть чётный делитель ( $d 2$ или $d2+ 1).$ Тогда $d2 =2$ и $n$ делится на 2 и на 3. Но тогда у $n$ есть делители $n∕2,$ $n∕3,$ $n∕6,$ то есть их сумма уже $n.$ Значит, $n∕6= 1$ и $n= 6$ является единственным ответом.

Ответ:

$n =6$

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

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

Все натуральные делители натурального числа разбили на пары и посчитали сумму чисел в каждой паре. Оказалось, что все суммы — простые числа. Докажите, что все они различны.

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

Подсказка 1.

Допустим, в одну пару попали числа, которые имеют общий делитель d > 1. Может ли тогда их сумма быть простым числом?

Подсказка 2.

Нет, не может. Это следует как раз из наличия общего делителя. Как тогда можно разбить делители исходного числа на пары?

Подсказка 3.

Числа в одной паре должны в произведении давать исходное. Чтобы это понять, нужно вспомнить, что не менее половины делителей числа делятся на простое p.

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

Заметим, что если $a +b$ является простым числом, то $a$ и $b$ взаимно просты. Далее докажем, что если $d 1$ и $d 2$ — два делителя числа $n$ и $d1d2 > n,$ то эти делители не могут быть взаимно просты. Рассмотрим $p$ такое, что его степень вхождения в $d1d2$ больше, чем в $n$ (оно есть, поскольку $d1d2 > n).$ Тогда $p$ должно делить и $d1,$ и $d2.$ Докажем, что в каждой паре делителей их произведение должно быть в точности $n.$ Пусть в какой-то паре оно меньше. Поскольку произведение всех делителей — это $n n2,$ найдётся пара, в которой произведение больше, чем $n.$ По доказанному, сумма этих двух делителей не может быть простым числом, противоречие. Итак, в каждой паре делителей их произведение одинаково. Поскольку делители различны, их суммы совпадать не могут, ведь пара чисел однозначно восстанавливается по сумме и произведению.

Курсы

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

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

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

Натуральное число $n$ дает остаток 4 при делении на 8. В ряд выписаны числа $1= d < d < ...< d = n 1 2 m$ — все делители $n$ . Докажите, что если число $k< m$ не кратно 3, то $dk+1 ≤2dk.$

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

Подсказка 1.

По условию число делится на 4, но не делится на 8. Допустим, что у n есть нечётный делитель d. Какие тогда ещё делители точно можно выделить?

Подсказка 2.

Это делители 2d и 4d. Значит, если k-ый делитель будет иметь вид d или 2d, то он точно подойдёт под условие. Тогда плохим может оказаться только делитель вида 4d.

Подсказка 3.

Если номер этого делителя не делится на 3, то найдётся тройка, минимальный делитель в которой лежит между d и 4d. Тогда подходящее число можно поискать в ней.

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

По условию число $n$ делится на 4, но не делится на 8. Тогда разобьём делители $n$ на группы следующим образом: возьмём в группу делители $d,$ $2d$ и $4d,$ где $d$ не делится на 2. Пусть минимальные числа в группах — это

1= s1 < s2 <...<sk = n∕4.

Номером группы будем называть индекс $s i$ из этой группы. Рассмотрим $d= d3x+y,$ где $y ∈ {1,2}.$ Если $d$ не делится на 4, то $d ≤2d, 3x+y+1$ поскольку $2d$ точно является делителем $n.$

Предположим теперь, что $d$ кратно 4. Пусть $a$ — номер группы, которой принадлежит $d.$ Заметим, что $a ≤x,$ поскольку число $4s x+1$ точно больше, чем $d , 3x+y$ ведь оно больше $3x$ чисел из групп с номерами, не более $a$ и больше, чем $s x+1$ и $2s . x+1$ Тогда есть хотя бы один делитель, меньший $d,$ номер группы у которого хотя бы $x+ 1$ (поскольку есть $3x$ чисел, меньших $d.)$ Рассмотрим наибольший из таких делителей $b.$ Тогда $b$ не может иметь вид $4s,$ поскольку $b< d.$ Значит, по выбору $b$ имеем $b< d< 2b.$ Остаётся заметить, что $2b$ является делителем $n,$ а значит, $2d ≥d3x+y+1.$

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

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

Натуральные числа $m$ и $n$ таковы, что $m +n +1$ — простое и делит число $2(m2 +n2)− 1.$ Докажите, что $m = n.$

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

Подсказка 1.

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

Подсказка 2.

Заметим, что n сравнимо с (-1−m) по модулю m+n+1. Заменив n в выражении, предстоит как-то воспользоваться простотой числа n+m+1.

Подсказка 3.

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

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

Пусть $m ⁄= n.$ Не умаляя общности, $n > m.$ Заметим, что

n ≡−1 − m (mod n+ m+ 1).

Заменим в выражении из условия $n :$

. 2m2 +2(1+ m)2− 1 .. n +m + 1

. (2m +1)2.. n +m + 1

Но так как $(m +n +1)$ — простое, то

2m + 1 ... n +m + 1

Но

0< 2m+ 1< n+ m +1

Получаем противоречие, а значит, требуемое верно.

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

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

Простые числа $a,$ $b,$ $c$ таковы, что $ab+ a+b$ делится на $c,$ $bc+b +c$ делится на $a,$ $ac+a +c$ делится на $b.$ Докажите, что среди чисел $a,$ $b,$ $c$ есть одинаковые.

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

Подсказка 1

Предположим, все числа различны. Что, если наименьшее число равно 2? Проанализируйте чётность выражений вида bc + b + c.

Подсказка 2

Если a ≥ 3, что можно сделать с тремя данными условиями делимости? Как собрать их в одно выражение, используя симметрию?

Подсказка 3

Рассмотрим выражение abc + ab + bc + ca + a + b + c. Почему оно "наследует" делимость на a, b и c из исходных условий?

Подсказка 4

Разделите выражение abc + ab + bc + ca + a + b + c на abc. Что получится? Как можно оценить сверху это выражение?

Подсказка 5

Воспользуйтесь тем, что (a + 1)(b + 1)(c + 1) = abc + ab + ac + bc + a + b + c + 1.

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

Предположим противное: все числа различны. Без ограничения общности считаем $a <b <c.$ Отдельно рассмотрим случай $a= 2.$ Тогда $b,c$ — нечетные простые, следовательно, $bc+b+ c$ — нечетное и не делится на $a,$ противоречие.

Пусть $a≥3.$ Тогда $b≥ 5$ и $c≥ 7.$ Теперь

abc+ab+ bc +ca+ a+ b+c

делится на $a,$ на $b$ и на $c,$ следовательно, оно также делится на $abc,$ но это невозможно, поскольку

abc+-ab+bc+-ca+-a+-b+-c a+-1 b+-1 c+-1 4 6 8 1< abc < a ⋅ b ⋅ c < 3 ⋅5 ⋅7 <2.

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

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

Натуральные числа $a,$ $b,$ $c,$ $d,$ $e,$ $f$ таковы, что $a< c < e, b d f$ при этом $af − be= −1.$ Докажите, что $d ≥b+ f.$

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

Подсказка 1

Рассмотрим дробь (a + e)/(b + f). Что мы знаем о её расположении относительно a/b и e/f? Проверьте разности (a + e)/(b + f) − a/b и e/f − (a + e)/(b + f). Как связано данное условие af − be = −1 со знаками этих разностей?

Подсказка 2

Можем ли мы представить c/d в виде (ax + ey)/(bx + fy) для некоторых натуральных x, y?

Подсказка 3

Рассмотрим систему, состояющую из уравнений bx + fy = d и ax + ey = c. Как выразить x и y, используя условие af − be = −1? Что можно сказать о знаках выражений de − cf и bc − ad, учитывая цепочку неравенств a/b < c/d < e/f?

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

Заметим, что

a a-+e e b < b+ f < f.

В самом деле,

a-+e − a = be− af-=-1---> 0 b+ f b b(b+ f) b(b+ f)

e− a+-e =-be-− af =--1---> 0. f b+ f f(b+ f) f(b +f)

В любом случае мы можем решить систему

({ ax+ ey = c (bx+ fy = d

умножая первое уравнение на $f,$ а второе на $e$ и вычитая первое из второго, получим уравнение

(be− af)x= de − cf =⇒ x =de− cf > 0,

так как

cd < ef ⇐⇒ de−dfcf-> 0

и аналогично имеем, что $y = bc− ad> 0.$

Таким образом, существуют натуральные числа $x$ и $y$ такие, что

c= ax+-ey, d bx+ fy

что влечёт

d =bx+ fy ≥ b+f.

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

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

Найдите все пары различных натуральных чисел $a$ и $b$ такие, что $b2+ a+1$ делится на $ab− 1.$

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

Подсказка 1.

В задачах на делимость x на y часто помогает поиск выражения, сравнимого с x по модулю y, абсолютное значение которого мало отличается от y.

Подсказка 2.

Если a > b, то само выражение отлично подходит на эту роль. Иначе хочется как-то избавиться от большого слагаемого b². Как это можно сделать?

Подсказка 3.

Докажите, что b является обратным остатком к a. Тогда мы можем заменить b на 1/a в нашей делимости и привести выражение к общему знаменателю.

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

Разберем два случая.

Пусть $a> b.$ Предположим, что частное от деления данных чисел не меньше 2. Тогда

2 b + a+ 1≥ 2(ab− 1),

откуда

2 2 b + b+ 1≥a(2b− 1)≥ (b+1)(2b− 1)=2b + b− 1.

Значит, $2≥ b2,$ откуда $b= 1.$ Значит $2+ a$ делится на $a− 1,$ откуда $3$ делится на $a − 1.$ То есть $a =2$ или $a= 4.$ Если же частное от деления равно 1, то

b2+ a+ 1= ab− 1,

откуда

b2+ 2= a(b− 1).

Тогда

b2+ 2≡ 3≡ 0 (mod b− 1),

откуда $b= 2$ или $b=4.$ В первом случае находим $a+ 5= 2a − 1,$ откуда $a= 6.$ Во втором случае находим $17+ a= 4a − 1,$ то есть $a =6.$

Теперь разберем случай $a< b.$ Тогда

a(b2+ a+1)≡ ab2+a2+ a≡ b+ a2 +a ≡0 (mod ab− 1).

Предположим, что частное от деления больше 1. Тогда

a2+ a+ b≥ 2(ab− 1),

откуда

a2+ a+ 2≥ b(2a− 1) ≥2a2+ a− 1.

Тогда $3 ≥a2,$ откуда $a= 1.$ Тогда $b+ 2$ делится на $b− 1,$ откуда снова $b= 2$ или $b= 4.$ Наконец, если частное от деления равно 1, то

2 b+ a + a= ab− 1.

Тогда

a2+a +1= b(a − 1).

Значит,

a2+ a+ 1≡ 1+ 1+1 ≡3 ≡0 (mod a− 1),

откуда $a= 2$ или $a= 4.$ В первом случае

4+ 2+ 1= 7= b.

Во втором случае $21= 3b,$ откуда $b= 7.$

Ответ:

$(1,2),$ $(1,4),$ $(2,6),$ $(4,6),$ $(2,7),$ $(4,7)$ и их перестановки

Интенсивы

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

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

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

Натуральные числа $a$ и $b$ таковы, что $a!b!$ делится на $a!+ b!.$ Докажите, что $3a≥ 2b+ 2.$

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

Подсказка 1.

Хотим сократить условие делимости на min(a, b)!, поэтому разумно рассмотреть случаи знака между a и b.

Подсказка 2.

Считаем a < b. В задачах на делимость x на y часто помогает мысль поиска множителей в x, взаимопростых с y. Это поможет уменьшить x и получить более содержательное утверждение.

Подсказка 3.

Получили, что a! делится на 1 + (a+1)·...·b, но тут ещё раз спасает наша мысль, ведь произведение b−a последовательных чисел делится на (b−a)!.

Подсказка 4.

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

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

Первое решение. Если $a >b,$ мы сразу получаем $3a≥ 2b +2.$ В случае $a= b,$ требуемое неравенство равносильно $a≥ 2,$ что легко проверяется, так как пара $(a,b)= (1,1)$ не удовлетворяет условию $a!+ b!|a!b!.$ Теперь предположим, что $a< b,$ и обозначим $c= b− a.$ Требуемое неравенство принимает вид $a≥ 2c+ 2.$

Предположим, от противного, что $a≤ 2c+ 1.$ Определим

b! M = a! = (a+ 1)(a+ 2)...(a+c).

Из условия $a!+ b!|a!b!$ следует $1 +M |a!M,$ откуда мы получаем $1+ M |a!.$ Заметим, что должно выполняться $c< a;$ в противном случае $1+M >a!,$ что невозможно. Мы видим, что $c!|M,$ так как $M$ — это произведение $c$ последовательных целых чисел. Таким образом, $НО Д(1+M, c!)= 1,$ откуда следует, что

|| 1+ M || a!-=(c+ 1)(c+2)...a. (1) c!

Если $a≤ 2c,$ то $a!c!-$ является произведением $a− c≤ c$ целых чисел, не превосходящих $a,$ тогда как $M$ является произведением $c$ целых чисел, превосходящих $a.$ Следовательно, $1+ M > ac!!,$ что является противоречием.

Остаётся исключить случай $a= 2c+ 1.$ Так как $a+ 1= 2(c+ 1),$ то $c+1 |M.$ Следовательно, из (1) мы можем заключить, что

1+ M |(c +2)(c+ 3)...a.

Теперь $(c+ 2)(c+3)...a$ является произведением $a− c− 1= c$ целых чисел, не превосходящих $a;$ таким образом, оно меньше, чем $1+ M.$ Снова мы приходим к противоречию.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Как и в предыдущем решении, мы можем предположить, что $a <b,$ и пусть $c= b− a.$ Предположим, от противного, что $a≤ 2c+ 1.$ Из условия $a!+b!|a!b!$ мы имеем

N =1 +(a+ 1)(a+ 2)...(a+ c) | (a+ c)!,

из чего следует, что все простые делители $N$ не превосходят $a +c.$

Пусть $p$ — простой делитель $N.$ Если $p≤ c$ или $p≥a +1,$ то $p$ делит одно из чисел $a +1,$ …, $a+ c,$ что невозможно. Следовательно, $a ≥p ≥c+ 1.$ Кроме того, должно выполняться $2p >a+ c;$ в противном случае,

a+1 ≤2c+ 2≤ 2p ≤a +c,

откуда $p|N − 1,$ что опять же невозможно. Таким образом, мы имеем $(a+c ] p ∈ -2-,a ,$ и $2 p ∤ (a +c)!,$ так как $2p> a+ c.$ Следовательно, $2 p ∤ N$ также.

Если $a≤ c+2,$ то интервал $(a+c ] -2-,a$ содержит не более одного целого числа и, следовательно, не более одного простого числа, которое должно быть равно $a.$ Так как $p2 ∤N,$ мы должны иметь $N = p= a$ или $N = 1,$ что абсурдно, поскольку $N > a≥ 1.$ Таким образом, мы имеем $a≥ c+ 3,$ и значит, $a+c2+1≥ c+2.$ Отсюда следует, что $p$ лежит в интервале $[c+2,a].$

Таким образом, каждый простой множитель, входящий в разложение $N,$ лежит в интервале $[c+2,a],$ и его степень в точности равна 1. Поэтому мы должны иметь

N |(c+ 2)(c+3)...a.

Однако $(c+ 2)(c+ 3)...a$ является произведением $a− c − 1≤ c$ чисел, не превосходящих $a,$ поэтому оно меньше, чем $N.$ Это противоречие.

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

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

Пусть $1= d < d < ...< d = n 1 2 k$ — все натуральные делители натурального числа $n.$ Оказалось, что

(d1+ 1)(d2+ 1)...(dk+ 1)

делится на $d1d2...dk.$ Найдите $n.$

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

Заметим, что $d +1 =n +1. k$ Это выражение не имеет общих делителей ни с одним $d . i$ Значит,

d1d2...dk |(d1+ 1)(d2+ 1)...(dk−1+ 1).

Ясно, что $di+1 ≥ di+ 1.$ Отсюда следует, что делимость возможна лишь когда $di+1 = di+1$ при всех $i=1,$ …, $k− 1.$ Рассмотрим равенство $d = d +1. k k−1$ Если делителя $d k−1$ не существует, то есть $k= 1$ или, что равносильно, $n = 1.$ Если существует, то $d = n k−1 p$ для некоторого простого $p.$ Значит, равенство примет вид $n= n +1. p$ Если $p ≥3,$ то $n + 1< n. p$ Если $p= 2,$ то $n =2.$

Ответ:

$n =1;2$

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

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

В строчку выписаны все натуральные делители числа $n$ в порядке возрастания: $1= d <d < ...< d = n. 1 2 k$ Оказалось, что при любом натуральном $i$ от $2$ до $k$ включительно либо $di$ делится на $di−1,$ либо $di− 1$ делится на $di−1.$ Докажите, что $n$ имеет не более двух различных простых делителей.

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

Предположим, что у $n$ есть хотя бы $3$ различных простых делителя $p< q < r.$ Пусть $q =d . i$ Заметим, что оба числа $n- di$ и $-n-- di−1$ делятся на $r,$ так как $r$ является простым и имеет место неравенство

di−1 <di = q < r.

Отсюда следует, что $--n-− 1 di−1$ не может делиться на $n-. di$ Значит, по условию $-n-- di−1$ делится на $n, di$ то есть $d i$ делится на $d . i−1$ Но $1 <d < q, i−1$ откуда получаем противоречие.

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

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

Дано натуральное число $t> 1.$ Найдите все натуральные числа $n,$ удовлетворяющие одновременно двум условиям:

$∙$ у числа $n$ не менее $t+2$ делителей;

$∙$ если выписать все делители $n$ по возрастанию от 1 до $n,$ то каждый делитель, начиная с $(t+ 1)$ -го, будет делиться на сумму $t$ предыдущих делителей.

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

Пусть $d < 1$ $d < 2$ …< $d k$ — делители $n.$ По условию $d k$ кратно

dk−1+ dk−2 +...+ dk−t.

Заметим, что $d = n, k$ а $d k−1$ — предмаксимальный делитель $n.$ Но

dk−1+ dk− 2+...+dk−t > dk−1.

Значит,

d = d + d + ...+ d . k k−1 k−2 k−t

Аналогично

dk−1 = dk−2+ dk−3+ ...+ dk−t−1.

Из этих равенств следует, что $dk =2dk−1− dk−t−1.$ Но

dk ≥2dk−1 > 2dk−1− dk−t−1,

потому что $dk$ отличается от $dk−1$ домножением на простое число.

Ответ:

таких $n$ нет

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

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

Пусть $d ,d,...,d 1 2 k$ $(k> 1)$ — некоторые различные натуральные делители натурального числа $n.$ Оказалось, что

dk − dk−1 = dk−1− dk−2 = ...= d2− d1

n =d1+ d2+ ...+ dk.

При каких $n$ это возможно?

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

Предположим, что существует такое $i,$ что $(d ,d )= m >1. i i+1$ Тогда все делители из набора делятся на $m.$ Давайте заменим $n$ на $n∕m,$ а каждое $di$ на $di∕m.$ Будем делать так до тех пор, пока существует такое $i.$

Итак, теперь $(di,di+1)=1$ для всех $i.$ Пусть, не умаляя общности

d1 <d2 < ...< dk.

Тогда

n= d1 +d2+ ...+ dk

кратно $dk−1dk.$ Если $dk−1 >k − 1,$ то

dk− 1dk ≥ kdk > d1+d2+ ...+ dk.

Значит, $dk−1 ≤k − 1.$ Дальше нужно рассмотреть несколько случаев.

Если $k= 2,$ то $n= d1+ d2,$ притом $d1 < d2 ≤ n2,$ откуда $d1+d2 < n.$

Если $k≥ 3,$ то можно рассмотреть $dk,$ которое будет равно $k.$ Тогда

n =1 +2+ ...+ k= k(k+-1). 2

У $n$ есть делитель $k− 1,$ то есть $k(k+ 1)$ должно делиться $k− 1.$ Значит, $k+ 1$ делится на $k− 1.$ Это возможно лишь при $k =2,3.$ То есть, $k =3,n= 6.$ Вспомним, что $n$ и все делители можно домножить на некоторое число и ничего не поменяется. Значит, подходят все $n,$ кратные $6.$

Ответ:

$n =6k,k∈ ℕ$

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

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

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

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

Можно ли выписать 90 различных трёхзначных чисел в ряд в порядке возрастания так, чтобы произведение любых двух подряд идущих чисел делилось на предыдущее число?

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

Разобьем все трехзначные числа на промежутки вида

2 2 2 a ,a + 1,...,a + a

и промежутки вида

2 2 2 a +a+ 1,a +a+ 2,...,(a+ 1) − 1,

для $a= 10,$ $11,...,31.$ Предположим, что в нашем ряду стоят хотя бы $3$ числа из одного промежутка первого вида: $x <y <z.$ Тогда если $yz$ делится на $x,$ то $Н ОД(x,y)⋅НОД (x,z)$ делится на $x.$ Но

НОД(x,y)≤y − x≤ a− 1,

а также

НО Д(x,z)≤ z− x ≤a.

Поэтому

НОД (x,y)⋅НОД(x,z)≤ a(a− 1)< a2 ≤ x,

что приводит к противоречию. Аналогично доказывается, что не могут быть выбраны $3$ числа из промежутка вида

a2 +a+ 1,a2 +a+ 2,...,(a+ 1)2 − 1.

Так как каждое трехзначное число содержится ровно в одном из данных промежутков, то всего выбрано не более $22⋅2⋅2 =88$ чисел. Противоречие.

Ответ:

нельзя

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

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

Натуральные числа $a,b,c,d,e$ и $f <a$ таковы, что $abd+1$ делится на $c,$ $ace+1$ делится на $b,$ $bcf +1$ делится на $a.$ Докажите, что если $d∕c< 1− e∕b,$ то $d∕c <1− f∕a.$

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

Из условия очевидно, что

НОД (a,b) =НО Д(b,c)=Н ОД(c,a)= 1.

Заметим, что

a |abd+ ace +bcf +1,

так как $a|bcf +1.$ Аналогично,

b|abd+ ace+bcf + 1

c|abd+ ace+bcf + 1

Из попарной взаимной простоты $a,b,c$ следует, что

abc|abd +ace+ bcf + 1 =⇒ abd+ace+ bcf + 1≥ abc.

Преобразуем неравенство из условия:

dc <1 − eb ⇐ ⇒ bd+ ec <bc,

а так как обе части целочисленные имеем $bd+ ec≤bc− 1,$ также $f ≤ a− 1,$ тогда

abd +ace+bcf + 1= a(bd+ ce)+ bcf +1≤ a(bc− 1)+bc(a − 1)+ 1=

2abc− a− bc+ 1< 2abc =⇒

abc≤ abd +ace+ bcf + 1< 2abc.

Так как

abc|abd+ ace+ bcf +1

имеем

abd+ ace+ bcf +1= abc.

Тогда

abc >bcf + abd =⇒ ac> cf + ad =⇒ d <1 − f . c a

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

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

Дано простое число $p> 3.$ Натуральные числа $a,b,c$ и $d$ таковы, что

a+ b= c+ d= p,

а число $abcd$ — точный квадрат. Докажите, что какие-то два из чисел $a,$ $b,$ $c$ и $d$ совпадают.

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

По условию $b=p − a,$ $d= p− c,$ без ограничения общности натуральные числа $a,c< p, 2$ тогда

2 abcd =a(p− a)c(p − c)= x,

где $x$ — некоторое целое число. Рассматривая по модулю $p:$

2 2 2 a(p− a)c(p− c)≡ a(−a)⋅c(−c)= ac ≡ x (mod p),

откуда $x ≡±ac (mod p),$ то есть $x= ±ac+ pk$ для некоторого целого $k.$ Тогда:

a(p− a)c(p− c)= (±ac+pk)2 = (ac± pk)2,

без ограничения общности можно считать

a(p− a)c(p− c)= (ac+ pk)2

Раскроем скобки:

ac(p2− p(a +c)+ ac)= a2c2+ 2acpk+ p2k2,

acp2− acp(a +c)+ a2c2 = a2c2+ 2acpk+ p2k2,

acp2− acp(a +c)= 2acpk+ p2k2.

Делим на $p:$

2 acp− ac(a +c)= 2ack+ pk ,

2 p(ac− k )= ac(a+ c+ 2k).

Поскольку $p$ простое и не делит $ac,$ то $p|(a+ c+2k).$ Оценим $k :$

(a+-p−-a)2 (p)2 (p )2 a(p − a)≤ 2 = 2 , c(p− c)≤ 2 ,

p4 p2 a(p− a)c(p − c)≤ 16, |ac+ pk|≤-4 ,

так как $2 0< ac< p4-$

− p <k < p. 2 4

Тогда:

− p< a+c +2k< 3p. 2

Так как $a+ c+ 2k$ делится на $p$ и лежит в $(−p,3p), 2$ возможны случаи:

a +c+ 2k= 0 (1) или a+ c+ 2k= p (2).

Случай (1): $a+ c+2k =0.$ Тогда:

p(ac− k2)= 0, ac= k2.

Из $a+ c= −2k:$

(a+ c)2 = 4k2 = 4ac =⇒ (a− c)2 =0 =⇒ a =c.

Следовательно, числа совпадают.

Случай (2): $a+ c+2k =p.$ Тогда:

2 2 p(ac− k )=ac⋅p =⇒ ac− k = ac =⇒ k= 0.

Тогда $a +c= p,$ что невозможно, так как $a+ c<p.$

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

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

Назовем натуральное число хорошим, если оно делится на два последовательных нечетных натуральных числа, больших $1.$ Докажите, что для любого натурального $n> 1000$ среди чисел от $1$ до $n$ менее $n 5$ чисел являются хорошими.

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

Подсказка 1

Найдите способ перечислить все хорошие числа. Как можно оценить их количество?

Подсказа 2

Если число делится на два последовательных натуральных числа, то оно делится и на их произведение. Как можно оценить количество чисел кратных 3*5? k(k+2) при произвольном нечетном k?

Подсказка 3

Их количество не превосходит n/15 и n/k(k+2) соответственно. При каком k таких чисел уже не найдется?

Подсказка 4

При k больше, чем √n. Как теперь можно оценить общее количество хороших чисел?

Подсказка 5

Оно не больше, чем сумма n/{3*5}+n/{5*7}+...+n{l(l+2)}. Как можно преобразовать данную сумму?

Подсказка 6

Воспользуйтесь тем, что 1/{k(k+2)}=1/{2k}-1/{2k+4}, чтобы преобразовать данную сумму. Наконец, воспользуйтесь ограничениями на n, чтобы доказать, что это число менее n/5.

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

Заметим, что число, делящееся на два последовательных нечётных натуральных числа, делится также на их произведение. Поэтому количество чисел от $1$ до $n,$ делящихся на $2$ фиксированных нечётных числа $k$ и $k+ 2$ не превосходит $--n-- k(k+2) + 1.$ Также заметим, что число, не превосходящее $n$ может делиться на $k(k+ 2)$ только в случае, когда $k(k+ 2)≤ n.$ Обозначим наибольшее нечетное число, не превосходящее $√- n,$ через $l,$ то есть для него верно, что $-n- l≤ l+2,$ а также $√ - l≤ n.$ Тогда суммарное количество хороших чисел не превосходит