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

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

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

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

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

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

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

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

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

Задача 1#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

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

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

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

Задача 2#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$

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

Задача 3#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

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

Задача 4#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

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

Задача 5#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

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

Задача 6#99641

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

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

Подсказка 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$

Курсы

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

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

Задача 7#77773

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

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

$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,$ поэтому есть хотя бы ещё один делитель.

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

Задача 8#79995

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

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

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