Тема ИТМО (Открытка)

Теория чисел на ИТМО

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

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

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

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

Подтемы раздела итмо (открытка)

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

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

Задача 1#121643

Найдите все пары числел $(p,n),$ где $p−$ простое, а $n−$ целое и при этом $p4+ 211= n2+ 5pn.$ В ответе укажите значения $n.$ Если их несколько, перечислите их в любом порядке через запятую.

Источники: ИТМО-2025, 11.6(см. olymp.itmo.ru)

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

Подсказка 1

Хотим использовать малую теорему Ферма (МТФ). Посмотрим на левую часть: по какому модулю удобно рассматривать остаток?

Подсказка 2

Рассматриваем остаток по модулю 5 (тогда возникает требование, что p не равно 5), так как по МТФ p⁴ дает остаток 1 по модулю 5. Вся левая часть, получается, дает остаток 2 по модулю 5. Теперь посмотрим на правую часть. Сразу видно, что второе слагаемое дает остаток 0 по модулю 5 (так как имеет вид 5*q). Что тогда можно сказать о n²?

Подсказка 3

Получается, n² должно давать остаток 2 по модулю 5. Рассмотрим различные случаи остатков. Какой вывод можем сделать?

Подсказка 4

Да, n² не может давать остаток 2 по модулю 5. Тогда у нас остается единственное возможное значение p: p = 5. Тогда наше уравнение превращается в квадратное, которое легко решается!

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

Согласно малой теореме Ферма, если $p⁄= 5,$ число $p4$ даёт остаток 1 при делении на 5. Число 211 также даёт остаток 1 при делении на 5. И $5pn$ делится на $5.$ Значит, если $p⁄= 5,$ мы получаем, что $2 n$ даёт остаток 2 при делении на 5, что невозможно.

Осталось разобрать случай $p =5.$ В этом случае нам надо решить квадратное уравнение

2 n +25n− 625 − 211= 0

−25±-√3125+-4⋅211 n1,2 = 2

Откуда получаем два решения: $(p,n)=(5,−44)$ и $(p,n)= (5,19).$

Ответ:

$− 44,19$

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

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

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

Задача 2#126992

Обозначим за $d(n)$ число натуральных делителей числа $n$ (включая единицу и само число). Найдите все такие $n,$ что $n =33⋅d(n)$

Источники: ИТМО - 2025, 10.8 ( см. olymp.itmo.ru)

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

Подсказка 1

Так как n представимо как 33 * d(n), то, не мудрствуя лукаво, легко понять, что n делится на 3 и на 11. Зная эти факты, можем записать, как будет выглядеть число n в разложении на простые множители.

Подсказка 2

Зная информацию из подсказки 1 и равенство из условия можно записать несколько уравнений. Подставив одно в другое, можно понять, что 3 и 11 могут входить в состав числа n только в очень маленьких степенях.

Подсказка 3

Да! Действительно. Пусть в состав числа n 3 входит в степени l, а 11 в степени k. Тогда надо разобрать всего 2 случая: k = l = 1; k = 1, l = 2. Осталось только аккуратно рассмотреть, что получается в этих случаях и какие из них реализуются.

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

Очевидно, $n$ делится на $3$ и на $11.$ Разложим $n$ в произведение степеней простых чисел:

l k k1 km n= 3 ⋅11 ⋅p1 ⋅...⋅pm

Тогда

d(n)= (l+1)(k+ 1)(k1+ 1)...(km + 1)

Разделив $n$ на $33⋅d(n)$ получим

3l−1 11k−1 pk11 pkmm l+1-⋅k+-1-⋅k1+1-...⋅km-+1 =1

Заметим, что все дроби в этом произведении, кроме первых двух, гарантированно не меньше $1$ (равенство достигается только в случае $1 12+1 =1$ ). Тогда как минимум одна из первых двух дробей не превосходит единицы, как и их произведение.

Вторая дробь не превосходит единицы только при $k= 1.$ В этом случае она равна $12.$ Первая же дробь может быть равна как $12$ при $l= 1,$ так и $2−1 32+1-=1$ при $l= 2.$ При этом при $k> 1$ вторая дробь составляет как минимум $131,$ а при $l> 2$ первая дробь составляет как миниумм $332+1 = 94.$ И то и другое больше двух, что делает произведение дробей больше единицы.

Осталось разобрать два случая: $k= l= 1$ и $k= 1,l= 2.$ В первом случае и первая, и вторая дробь равны $12,$ а их произведение составляет $14.$ Значит, произведение остальных должно быть равно $4.$ Множитель $2$ в числителе может получиться только одно из оставшихся простых чисел равно $2.$ Рассмотрим дроби вида $2k1, k1+1$ которые не превосходят $4,$ это :

-21- 1+ 1 = 1

22 4 2+-1 = 3

3 -2--= 2 3+ 1

-24- = 16-= 31 4 +1 5 5

Нас устраивают только дроби, у которых после сокращения в числителе остаётся хотя бы $4.$ Если мы используем дробь $4, 3$ нам понадобиться ещё один множитель $3$ в числителе, которого у нас нет, если же возьмём $16- 5 ,$ нам понадобится ещё дробь с $5$ в числителе, то есть минимум $5 2,$ что уже даёт слишком большое произведение.

Во втором случае первая дробь равна $1 2,$ а вторая равна $1.$ Значит, произведение остальных должно быть равно $2.$ Мы можем добавить к ним только $-23- 3+1 = 2$ и получить единицу в качестве произведения.

Значит,

l k 3 2 3 n= 3 ⋅11 ⋅2 = 3 ⋅2 ⋅11= 72⋅11= 792

Ответ:

$792$

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

Задача 3#82288

Натуральные делители натурального числа $n$ занумеровали по возрастанию: $d = 1, d ,...,d = n 1 2 k$ . Оказалось, что $d =120 18$ . Какое наименьшее значение может принимать число $n$ ?

Источники: ИТМО-2024, 11.3 (см. olymp.itmo.ru)

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

Подсказка 1

Первое, что хочется сделать, это разложить 120 на множители. Получается, что все его 16 делителей будут и делителями исходного числа. А что будет, если наше исходное число будет делится, например, на большую степень двойки?

Подсказка 2

Давайте посмотрим. Если n делится на 2^4, то к делителям n прибавится ещё 3 делителя, меньшие 120. Получается, что 120 не будет восемнадцатым делителем. Противоречие. Аналогично рассматривая 3 и 5, может ли n делится на их большие степени? Какой вывод из этого можно сделать?

Подсказка 3

Да, получаем и там аналогичное противоречие. Значит, у n есть простой делитель p, кроме 2, 3 и 5. Если мы сможем оценить его, то задача решена. Нельзя ли почти с помощью почти аналогичного противоречия получить оценку на p?

Подсказка 4

Верно, если у числа будут делители p, 2p и 3p, меньшие 120, то получается снова, что 120 минимум девятнадцатый делитель. Осталось только найти наименьший простой делитель, больший 40, посчитать ответ, и победа!

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

У числа $120 =23⋅5⋅3$ шестнадцать делителей и все они являются делителями числа $n$ . Если $n$ делится на $24$ , то к этим делителям добавляются ещё числа 16,48 и 80 , то есть 120 — это уже как минимум девятнадцатый делитель.

Если $n$ делится на $2 3$ , то к исходным шестнадцати делителям добавляются 9,18 и 45 . Если $n$ делится на $2 5$ , то к исходным шестнадцати делителям добавляются 25,50 и 75.

Значит, $n$ делится на какое-то простое число $p$ , кроме 2,3 и 5 . Если это число не превосходит 40 , то числа $p,2p$ и $3p$ являются делителями $n$ , меньшими 120 , и мы опять получаем слишком много делителей. Значит, $p$ хотя бы 41 , то есть $n≥ 120⋅41$ . Заметим, что это число нас как раз устраивает.

Ответ: 4920

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

Задача 4#68640

Простые числа $p,q$ и $r$ таковы, что

2 2 2 p< q,p +q =r,p +q = r − 116

Найдите $p,q$ и $r.$

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

Подсказка 1

Есть условие на сумму p+q, есть условие на сумму их квадратов, что хочется сразу сделать?

Подсказка 2

Возвести в квадрат p+q! Тогда будет нетрудно выразить 2pq, получившиеся в квадрате суммы. Каким условием мы еще не пользовались?

Подсказка 3

Простотой p и q! 2pq = 116 = 4 * 29. Остается лишь разобрать пару случаев)

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

Возведём первое равенство в квадрат:

2 2 2 p +2pq+ q = r

Далее вычтем из полученного второе исходное равенство:

2 2pq =116= 2 ⋅29

Значит, учитывая, что $p< q,$ получаем:

p= 2,q = 29⇒ r= p+ q = 31

Ответ:

$p =2,q = 29,r= 31$

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

Задача 5#68709

Последовательность $x n$ задана рекуррентным соотношением $x = x + {x } n+1 n n$ и начальным условием $x = 1-. 0 67$ Найдите $[x66000].$

( $[a]$ — целая часть числа $a,$ ${a}$ — дробная часть числа $a).$

Источники: ИТМО-2023, 11.7 (см. olymp.itmo.ru)

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

Подсказка 1

Дробная часть, целая часть, ну и ну… А x_(n+1) = x_n + {x_n}, то чему равно x_(n+1) если использовать только дробные и целые части числа, а не само число?

Подсказка 2

Верно, x_(n+1) = [x_n] + 2*{x_n}. Значит, если смотреть только на дробную часть, то нетрудно доказать, что она будет равна дроби со знаменателем 67, а также, что числители дроби будут являться циклом, если рассмотреть последовательность целиком(как минимум, потому, что числитель n-ого члена последовательности сравним по модулю с 2^n, а остатки у 2^n по модулю 67 образуют цикл). А что можно тогда сказать, про члены, разность индексов которых равна 1 циклу?

Подсказка 3

Верно, во-первых, что(если длина цикла k и мы берем i-ый элемент), то {x_(i+k)} = {x_i}. Но тогда из этого следует, что x {x_(i+k)} - {x_i} = {x_(i+2k)} - {x_(i+k)}, так как {x_(i+2k)} = {x_(i+k)}. При этом, так как нам неважно, какая разность была между {x_(i+k)} и {x_i}, для вычисления x_(i+k+1), так как влияет только дробная часть, то будет выполнено, что

Подсказка 4

Верно, что можно просто найти эту разность(и цикл) и понять, в каком по порядке циклу лежит x_66000 и чему он соответствует в первом цикле и мы сможем в явном виде найти x_66000. Как это сделать? Начать писать все x_i, начиная с нулевого, пока в числителе дробной части не будет 0. А значит, осталось перебрать 66 значений(10 минут) и найти нужные значения!

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

Пусть оказалось так, что ${x }= {x} k+i i$ для некоторого $k >0$ . Тогда выполнено $x − x = x − x k+i i 2k+i k+i$ . Действительно, на каждой следующей итерации мы учитываем только дробную часть исходного числа (целая же часть определяет только нашу “точку старта”). Поэтому выполнено равенство ${x2k+i}= {xk+i}$ . Также отсюда будет следовать $[xk+i]− [xi]= [x2k+i]− [xk+i]$ , то есть наш сдвиг по целой части будет таким же. Нетрудно видеть, что оба условия вместе дадут $xk+i− xi = x2k+i− xk+i$ (если известно ${xk+i}= {xi}$ ). Далее остаётся только найти цикл нужной длины. Оказывается, что $1 x66 = 337$ и выполнено ${x0}= {x66}$ , мы получили цикл, получаем

[x66000]= [x0+66⋅1000]= 1000 ⋅([x66− x0])= 1000⋅33= 33000

Замечание. Как же найти такой цикл, не считая вручную все $66$ значений до него? Во-первых, уже $66 1- {x33}= 67 = 1− 67$ , что явно нам намекает, когда мы снова встретим единицу (по сути мы каждый раз умножаем дробную часть на 2, поэтому можно сразу сделать вывод, что на $66$ шаге, поскольку за столько же шагов результат возведётся в квадрат по модулю $67$ ). Во-вторых, уже на шестом шаге мы получим $3- {x6}= 1− 67$ , поэтому далее можно попробовать идти по кратным шести индексам, чтобы быстрее добраться до $66$ . Почему вообще всё это имеет смысл? Потому что $66000$ делится и на 6, и на 33, и на 66 — именно в них мы и ждём больше всего увидеть цикл, чтобы задача после этого решилась быстро и легко.

Ответ: 33000

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

Задача 6#88135

Сумма двух различных натуральных делителей натурального числа $n$ равна 100. Какое наименьшее значение может принимать число $n?$ (Среди указанных делителей могут быть единица и само число.)

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

Подсказка 1

Предположим, что мы взяли какие-то два делителя числа n числа и сложили их. Если каждый из этих двух делителей меньше n, то он меньше n “в сколько-то раз”. Какой вывод мы тогда сможем сделать для их суммы?

Подсказка 2

Да, в таком случае сумма этих двух делителей, равная ста, будет меньше, чем n, следовательно, n больше ста. Это не очень удовлетворительный результат, потому что первый пример, приходящий в голову — 99+1 — это пример меньше, чем на 100. Какой вывод можно отсюда сделать?

Подсказка 3

Тогда получается, что один из делителей заведомо равен самому числу. В таком случае, введя d как меньший делитель, можно записать условие в виде достаточно простого выражения!

Подсказка 4

Из нашей записи получится, что n/d+1 должно быть делителем числа 100. При этом для каждого фиксированного d чем больше n/d, тем больше n. Отсюда и получим искомый ответ!

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

Если один из наших делителей — само число $n$ , а второй — некоторое число $d$ и $n= dk$ , то мы получаем

100= d+ dk =d(k+ 1)

n ( 1) 100= n+ k = n⋅ 1+ k

Чем $k$ больше, тем и само $n$ больше.

Наименьшее $k >1$ такое, что $k+ 1$ является делителем 100, это 3. При таком $k$ получаем $n =75$ .

Если же $n$ нет среди двух наших делителей, то $n n 2 + 3 ≥100$ , откуда $n ≥120$ .

Ответ: 75

Курсы

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

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

Задача 7#74576

$427000− 82$ делится на $3n.$ Какое наибольшее натуральное значение может принимать $n?$

Источники: ИТМО-2022, 11.3 (см. olymp.itmo.ru)

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

Подсказка 1

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

Подсказка 2

Верно, это значит, что наше число делится на n-ую степень, но не делится на (n+1)-ую. Через сравнения тут решить, наверное, не получится. Но можно же попробовать выразить наше число в явном виде через сумму, где будет видна степень тройки. Какую формулу хорошо бы не побояться применить?

Подсказка 3

Да, конечно, это формула бинома Ньютона. Можно представить 4=3+1 и раскрыть скобки. Достаточно раскрыть первые 5-6 скобок, потому что в дальнейшем степени будут большими, а вот первые члены можно проанализировать, выделив степени тройки. Осталось только найти член в выражении, который не будет делиться на большую степень тройки в отличие от других, и победа!

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

27000 27000 27000⋅26999-⋅32- 27000⋅...⋅26998⋅33- 4 =(1+ 3) = 1+ 27000⋅3+ 2 + 6 +

27000⋅...⋅26997⋅34 27000 ⋅...⋅26996⋅35 + ------24-------+ -------120-------...

Два последних выписанных слагаемых делятся на $36,$ как и все остальные слагаемые, заключённые в многоточие.

2 3 1+ 27000⋅3+ 27000⋅26999-⋅3--+ 27000⋅26999⋅26998⋅3-= 1+ 81000+ 2 6

+27000⋅26999⋅32+27000⋅26999⋅26998⋅32 2

Заметим, что

1+ 81000= 1+ 81(1+ 999)= 1+ 81+ 81 ⋅999= 82+ 81 ⋅999

Это даёт остаток $82$ при делении на $36,$ так как последнее слагаемое делится на $36.$

2 2 2 27000⋅26999-⋅3-+-272000⋅26999-⋅26998⋅3-= 27000⋅26999⋅32-⋅(1+26998)-

А это число, очевидно, делится на $35,$ но не на $36.$ Значит, $427000 − 82$ также делится на $35,$ но не на $36.$

Ответ: 5

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

Задача 8#99641

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

Источники: ИТМО - 2021, 11.2 (см. olymp.itmo.ru)

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

Подсказка 1

В условии задачи сказано, что надо просуммировать числа от 1 до 3000, которые не взаимнопросты с 3000. Какие нам тогда числа не подходят, если 3000 = 2³ * 3¹ * 5³?

Подсказка 2

Это значит, что нам подходят числа, которые делятся на 2, или на 3, или 5. Давайте поймём, что если нам подходит число x, то подходит и число 3000-x. При том, все числа, которые подходят под условие выше, разбиваются на пары. Или почти все? А когда тогда посчитать их сумму?

Подсказка 3

Числа 3000 и 1500 не составляют те самые пары, а вот все остальные числа, подходящие под условия все таки разбиваются на пары. Это значит, что нам теперь достаточно найти количество таких чисел и домножить их на 3000 (учтя особую роль в этой сумме исключений выше). Как найти количество таких чисел? Мы ведь не можем просто сложить количество чисел кратных 2, 3 и 5 и получить ответ. У нас есть числа которые кратны сразу двум каким-то, а также числа, кратные сразу всем. Подумайте, как тогда считать их количество?

Подсказка 4

Мы можем посчитать с помощью формулы включений и исключений количество таких чисел, а именно сначала количество просто кратных какому-то, минус сумма кратных сразу двум и плюс сумма кратных всем трём. Получится 2200. Чему тогда равна наша сумма?

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

$3000= 23 ⋅3 ⋅53$ , то есть нас интересуют числа, деляющиеся на $2,3$ или $5.$ Найдём сначала количество таких чисел. Для этого воспользуемся принципом включений и исключений. Чётных чисел от $1$ до $3000$ ровно $3000 2 = 1500$ , кратных трём — $3000 3 =1000$ , кратных пяти — $3000 5 =600$ . Однако, если просто сложить числа 1500,1000 и 600 , мы посчитаем некоторые числа 2 раза, а именно, числа, делящиеся на $2⋅3= 6,2⋅5= 10$ и $3⋅5= 15$ , поэтому из полученной суммы надо вычесть $3000 6 =$ $3000 500,10 = 300$ и $3000 15 = 200$ . Однако, $1500+1000+ 600− 500− 300− 200=2100$ всё ещё неправильный ответ, Поскольку в этом выражение числа, имеющие все три простых множителя, сначала считаются три раза, а потом их количество вычитается опять же три раза, поэтому надо снова добавить эти числа. Количество таких чисел $3000 − 2⋅3⋅5 =100$ , значит, количество чисел, имеющих с $3000$ общие делители и не превосходящих его, это $2200.$

Заметим теперь, что если какое-то число $x$ имеет с числом $N$ общие делители, то число $N − x$ тоже имеет с $N$ те же самые общие делители. Значит, все интересующие нас числа, кроме чисел $1500$ и $3000,$ разбиваются на пары с суммой $3000$ (числу 3000 в пару пришлось бы сопоставить $0,$ а числу $1500−$ само себя). Таких пар получаается $1099,$ поэтому итоговый ответ $1099⋅3000+ 3000+ 1500 =$ $1100⋅3000+ 1500 =3301500.$

Замечание.

Числа, меньшие $3000$ и взаимно простые с ним разбиваются на пары таким же образом, поэтому участники, знакомые с функцией Эйлера, могли получить формулу для ответа в виде

N(N +-1)−-N ⋅φ(N). 2

Ответ:

$3301500$

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

Задача 9#77773

Докажите, что число $33n+ 173n +313n$ при нечётном $n$ раскладывается в произведение хотя бы четырёх (не обязательно различных) натуральных чисел, больших единицы.

Источники: ИТМО - 2020, 11.1 (см. olymp.itmo.ru)

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

Подсказка 1

Нам нужно найти числа, на которые делится наше выражение. Попробуйте рассмотреть маленькие числа: на 2 выражение не делится, а на 3?

Подсказка 2

Верно, оно делится на 3, но что насчёт каких-нибудь степеней тройки? Рассмотрите наше выражение по модулю 9. Не забудьте, что каждое из слагаемых в нечётной степени.

Подсказка 3

О, оно делится на 9, здорово. Теперь надо найти ещё какой-нибудь делитель. Мы знаем, что одно из трёх слагаемых делится на 17. А кратна ли 17 сумма остальных двух слагаемых?

Подсказка 4

Попробуйте доказать, что a^m+b^m кратно a+b при нечётном m. Тогда доказать делимость на 17 будет совсем просто:) Вот, у нас есть уже три множителя, а четвёртый можно явно не искать, достаточно показать, что он будет больше единицы.

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

$3+ 31= 34$ делится на $17,$ а значит то же самое выполняется и для суммы любых нечётных степеней. Это верно, т.к. $am + bm$ на $a+ b$ при нечётном $m.$ По-другому можно это доказать так: $31≡ −3(mod 17),$ значит $3n 3n 3n 31 ≡ (−3) ≡ −3 ,$ т.к. $3n$ нечётно.

Теперь рассмотрим остатки по модулю $9.$ $3n 3$ делится на $9.$ $17$ в нечётной степени даёт при делении на $9$ остаток $8$ , а в чётной - остаток $1.$ Число $3 31$ даёт остаток $1$ при делении на $9,$ а значит и любая нечётная степень куба даёт такой же остаток. Таким образом, сумма $3n 3n 3n 3 + 17 + 31$ делится на $9.$

Мы получили уже три множителя: $3,3 и 17.$ Кроме того $3n 3n 3n 3 + 17 + 31 >3⋅3⋅17= 153,$ поэтому есть хотя бы ещё один делитель.

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

Задача 10#79995

Девочка Катя не любит число $239.$ Она выписала несколько различных чисел, ни одно из которых не содержит последовательность цифр $239$ (подряд и именно в таком порядке). Докажите, что сумма обратных к этим числам не больше $30000.$

Источники: ИТМО 2019

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

Количество подходящих $3n+ 1$ -значных чисел не больше, чем $9 ⋅999n :9$ вариантов для первой цифры и не более 999 вариантов для каждой следующей тройки цифр. Каждое из них не меньше $3n 10 .$