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

Подсказка 1

Давайте немного усложним себе задачу (на самом деле облегчив этим поиск) и будем пытаться найти число которое делится на n, и ещё одно, которое делится на m.

Подсказка 2

Очевидно, среди n последовательных чисел всегда найдется число, делящееся на n, а так как m<n, то и для m найдется. Но есть загвоздка…

Подсказка 3

Что делать, если эти числа совпадают? Попытайтесь найти ещё одно такое число.

Подсказка 4

Пусть НОД(m,n)=d. Докажите, что среди n последовательных натуральных чисел найдется число 2d.

Подсказка 1

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

Подсказка 2

Отлично! Теперь мы получаем, что наше число равно (102*7776ⁿ - 1)(102*7776ⁿ - 1). Попробуем подставить небольшие значения n. Что можно заметить про делители нашего числа?

Подсказка 3

Мы понимаем, что n = 0 точно подходит. Скобки (102*7776ⁿ - 1) и (102*7776ⁿ - 1) взаимно простые, а также наше число всегда делится на 101. Тогда стоит рассмотреть его по mod 101.

Подсказка 4

Попробуйте отдельно посмотреть на случаи, когда n чётно и нечётно, и в каждом из них применить неиспользованное ранее условие про количество различных простых множителей!

Подсказка 1

Изначально у нас "слишком много свободы". Работать с тремя независимыми переменными трудно. Давайте считать, что число a уже дано. Как это помогает причесать исходное условие?

Подсказка 2

Числа b и c встречаются в исходном равенстве дважды, поэтому следить за ними не так просто. Можно ли преобразовать исходное равенство таким образом, чтобы они встречались в новом не более одного раза (число а при этом может встречаться произвольное число раз, мы же считаем его данным)?

Подсказка 3

Да, исходное равенство можно представить в виде n+a² = (b+a)(c+a). Как теперь можно сформулировать условие представимости для данных n и а?

Подсказка 4

Необходимо и достаточно, чтобы число n+a² представлялось в произведение двух натуральных, где каждое больше а. Вспоминая, что а произвольное, достаточно показать, что для данного n существует хотя бы одно a, для которого число n+a² раскладывается в произведение двух натуральных, где каждое больше а. Как исходя из этого, можно воспользоваться условием делимости n на k²?

Подсказка 5

Хотим положить a таким образом, чтобы каждое из двух множителей делилось на k. При этом a мы хотим сделать не очень большим, чтобы сделать множители большими, чем a было не очень сложно. Как это можно сделать?

Подсказка 6

Можно взять a наименьшим делителем k. Пусть n = lp² при некотором простом p. Докажите, что при l+1 > p работает соображение предыдущей подсказки. Как выглядят остальные случаи?

Подсказка 7

Число n представимо в виде (q-1)p² при некотором простом q < p+1. Разберем случай q < p. Воспользуйтесь представлением p = mq+r для натуральных m и q и преобразуйте полученное равенство.

Подсказка 8

Осталось разобраться со случаем p = q. Помните, что мы еще не пользовались условием на n>20.

Подсказка 1

Для каких чисел удобно находить НОК?

Подсказка 2

Для наборов, в которых много единичек!

Подсказка 3

Можно сделать все числа, кроме одного, сделать единицами. Попробуем из равенства подобрать оставшееся!

Подсказка!

Мы знаем интересное свойство факториала - он делится на все числа до него. То есть все наши факториалы делятся на 2, 3, 4.... до 30! Попробуйте рассмотреть числа по какому-нибудь полезному модулю

Подсказка 1

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

Подсказка 2

Верно, знаменатель кратен какому-то из простых делителей числа 1001. Пусть этот делитель равен p. Если бы мы хотели опровергнуть слова семиклассника, то скорее всего слова о том, что дробь сократилась впервые, верно?

Подсказка 3

Нужно найти такое число, которое выражается через слагаемые n и p и при этом делится на p. Хороша идея взглянуть на знаменатель дроби.

Подсказка 4

Мы обнаружили число n + p - 1, которое делится на р. Это как будто знаменатель дроби через р-1 минуту. А что с её числителем? Найдём противоречие, которое искали в подсказке 2?

Подсказка 1

Разложим 1400 на простые множители, чтобы посмотреть, какие вообще наборы цифр есть для того, чтобы составить нужные по условию числа.

Подсказка 2

Отлично, получается 3 набора: "22255711", "42557111" и "85571111". Перестановкой цифр в каждом наборе мы получаем нужное число. Поработаем с первым набором: допустим, в нем все цифры разные, тогда подошло бы 8! чисел. Но теперь заметим, что не все цифры одинаковые, например, двойки повторяются 3 раза. Это значит, что на самом деле подходящих чисел в 3! раз меньше. То же проделаем и с пятерками (и с единичками тоже).

Подсказка 3

Отлично, в первом наборе получили 8! / (3! * 2! * 2!) вариантов. Аналогично считаем варианты и в втором, и в третьем наборах. Теперь остается сложить все эти варианты и получить итоговый ответ.

Подсказка 1

Мы знаем, что дробь a/b несократима тогда и только тогда, когда НОД(a, b)=1. Пусть a=m(n+1)+1, b=m(n+1)-n. Какой алгоритм мы должны проделать, чтобы найти НОД(a, b)?

Подсказка 2

Конечно, алгоритм Евклида! Получается, что наш НОД равен НОД(n+1, m(n+1)-n). Видно, что m(n+1)-n имеет остаток 1 при делении на n+1. Подумайте, когда такое может быть, и завершите доказательство!

Подсказка 1

Каким способом можно доказать, что состояние фиксированного объекта в процессе его изменения не приведёт к тому, что он примет начально состояние?

Подсказка 2

Найти полуинвариант! Давайте найдем величину, которая будет меняться монотонно в ходе процесса, и, как следствие, не вернется к изначальному состоянию.

Подсказка 3

Как найти полуинвариант в данной задаче? В условии задачи сказано, что при замене двух чисел x и y на их сумму x+y, второе число равно x-y или y-x. Было бы хорошо, если бы наш полуинвариант вел себя одинаково вне зависимости от этого выбора. Ясно, что данные числа равны по модулю. Как это помогает найти полуинвариант?

Подсказка 4

Пусть S является искомым полуинвариантом. Ясно, что S - это функция от набора чисел, написанных на доске в данный момент. Если мы положим в качестве S функцию от их квадратов, то значение S будет совпадать при выборе любой из разности чисел (x-y или y-x), что является хорошим знаком. Осталось доопределить S.

Подсказка 5

Самые естественные функции от набора переменных - их сумма или произведение. С суммой в данном случае работать проще (итак, в качестве предполагаемого полуинварианта мы пока положим S - сумму квадратов чисел написанных на доске), поскольку мы можем легко получить значения данного полуинварианта на каждом ходу. Поймите, как это можно сделать.

Подсказка 6

Если на доске были написаны числа x² и y², то сумма их квадратов измениться на (x-y)²+(x+y)²=2(x²+y²). Таким образом, значение S после каждого шага увеличивается вдвое. Осталось показать, что не существует двух различных последовательностей из 2n идущих подряд чисел таких, что отношение сумм их квадратов равно степени двойки. Каким способом это возможно сделать?

Подсказка 7

Мы можем показать, что степень вхождения двойки в сумму квадратов 2n последовательных чисел является инвариантом для данного n. Для этого можно явно показать, как степень вхождения двойки в рассматриваемую сумму зависит от n.

Подсказка 8

Пусть 2n=l*2^k, где l - нечетное натуральное число, k - натуральное число, не меньшее 1. Докажите, что степень вхождения двойки в сумму квадратов 2n последовательных чисел равна k-1.

Подсказка 9

Искомую сумму можно представить как l сумм 2^k последовательных квадратов натуральных чисел. Если мы докажем, что каждая из них имеет вид 2^{k-1}t, для некоторого нечетного числа t, то явно получим, что и вся сумма делится на 2^{k-1}, но не делится на 2^k. Сделайте это!

Подсказка 10

Рассмотрим сумму последовательных 2^k квадратов по модулю 2^k. Квадраты этих чисел имеют тот же набор остатков при делении на 2k, что и набор чисел 1², 2², 3²,..., (2^k)², а значит сравнимо по этому модулю c суммой 1²+2²+...+(2^k)². Каким образом ее можно преобразовать?

Подсказка 11

По известной формуле суммы квадратов первых n чисел, 1²+2²+...+(2^k)²=2^{k-1}(2^k+1)(2^{k+1}+1)/3 - кратно 2^{k-1}, но не кратно 2^k. Это как раз то, что мы хотели показать!

Подсказка 1

Нам нужно разложение на простые множители натурального числа и мы знаем его количество делителей. Может, есть подходящая формула, которая свяжет условия задачи?

Подсказка 2

Получили равенство, где с одной стороны стоит 2020, а значит, обе части делятся на 101, и мы хотим найти наименьшее натуральное подходящее число. Что это может значить?

Подсказка 3

С 101 разобрались, остались случаи с 2²*5. Аккуратно рассматриваем случаи и находим наименьшее число!

Подсказка 1

В этой задаче достаточно привести хотя бы один пример и обосновать его корректность. Попробуем подойти к такому примеру! Первым шагом нужно понять, а на что должно делиться число. Ага, сразу можем назвать последнюю цифру числа, уже что-то. Сможем привести пример, где все цифры встречаются только один раз?

Подсказка 2

Обратим внимание на 101. Нам нужен просто пример (необязательно наименьшее число), надо взглянуть на числа, которые делятся на 101. У многих из них повторяются цифры (2020, 2121, 3030, 4343 и др), а ведь нам как раз нужен пример, где всех цифр одинаковое количество!

Подсказка 3

Мы на финишной прямой! Осталось только собрать такой пример (мы уже поняли, что каждой цифры должно быть по две), осталось не забыть, что число должно не только оканчиваться на ноль, но и делиться на 4

Подсказка 1

Какой вид может иметь число N?

Подсказка 2

Пусть N = 5ᵏ ⋅ m, где m не делится на 5.

Подсказка 3

Обозначим d(a) как количество делителей a. Вычислите d(N) и d(5N).

Подсказка 4

d(N) = (k + 1)d(m), d(5N) = (k + 2)d(m). Запишите соотношение и подберите m.

Подсказка 1

В таких задачах стоит иногда попробовать подобрать какие-то варианты. И здесь начнем замечать интересное: если есть простым делителем 5 или, например, 7, тогда новое число не делится на 5 или 7. Обобщим эту догадку.

Подсказка 2

И действительно, при р > 3 всегда будут проблемы при делении числа N на р. Представьте N в виде произведения двоек и троек, где двойки войдут со степенью, например, k.

Подсказка 3

Да, получится N = 2^k * 3^(10-k), а теперь фокус: двойки превращаются в тройки, а тройки - в четверки, то есть в двойки в квадрате! Остается найти k, и так получим ответ!

Подсказка 1

Предположим, что могло! Значит были изначально какие-то три числа (a < b < c), превратившиеся в одинаковые. Что можно сказать про НОД, которые к ним прибавили?

Подсказка 2

Поняли, что добавленный к a НОД — делитель c - b! Какую оценку тогда можно сделать?

Подсказка 3

Получим, что a + НОД < c!

Подсказка 1

Наши числа имеют вид (4062-x)/x. Нам надо найти количество целых чисел, когда x пробегает от 1 до 4061. Как вы думаете, при каком условии на x это число будет целым?

Подсказка 2

(4062-x)/x = 4062/x - 1. Тогда нужно всего лишь обеспечить целость числа 4062/x. Стало быть x- делитель 4062. Посчитайте количество делителей числа 4062 (только не забудьте, что x<4062) и радуйтесь жизни!

Подсказка 1

Ну, во-первых, нужно обрести понимание о том, как устроены наименьшие собственные делители. Для этого вспомним, что по Основной Th. Арифметики n = p₁^a₁*p₂^a₂*...*p_k^a_k (p₁ < ... < p_k) для любого натурального n. Тогда какой наименьший собственный делитель?

Подсказка 2

Верно! Это p₁. Что насчёт следующего по величине собственного наименьшего делителя?

Подсказка 3

Очевидно, что это не p₃, p₄ и т.д. Значит это что-то связанное с p₂ или p₁, причём очевидно, что степень тоже не больше 2. Итого?

Подсказка 4

Верно, либо p₁^2, либо p₂. Пусть эти два наим. делителя это a и b. Что тогда можно сказать про наибольшие собственные делители?

Подсказка 5

Так точно! Это n/a и n/b. Теперь стоит рассмотреть случаи.

Подсказка 6

1-ый случай. a = p₁, b = p₂ - простые. Тогда p = (n/a + n/b) - a - b, где p - простое. То есть pab = (n - ab)(a+b). Посмотрим на делимость, не забывая о том, что a, b, p - простые.

Подсказка 7

Проделайте это сами и поймите, что p = (p₁+p₂). Отсюда в силу чётности и простоты: p₁ = 2, n = 4p₂. Отсюда найдите ответ. Попробуйте разобрать второй случай самостоятельно.

Подсказка 8

2 случай. a = p₁, b = p₁^2. Тогда аналогично получаем, что p₁^2*p = (p₁ + 1)(n - p₁^3). Теперь осталось немного.

Подсказка 9

Воспользуйтесь взаимной простотой p₁ и p₁ + 1 и решите задачу) Успехов!

Подсказка 1

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

Подсказка 2

Верно! Число 97 входит только в 4 факториала. Тогда, чтобы создать куб, один из них нужно вычеркнуть. А можно ли посмотреть теперь на какое-то другое простое число?