Теория чисел на ЮМШ

1. По МТФ , но в то же время и .

_________________________________________________________________________________________________________________________________________________________________________________

2. Если , то всё ясно. Если , то остальное как в предыдущем пункте. Иначе же . Например, потому что из МТФ , значит,

Тогда

______________________________________________________________________________________________________________________________________________________

3. Случаи разбираются руками. Дальше, аналогично предыдущим пунктам, если , то всё ясно. Иначе , а тогда для

Если бы остатки не повторялись, каждый бы встречался по разу, и тогда их сумма была бы равна 0 . Но тут, как мы видим, их сумма равна

_________________________________________________________________________________________________________________________________________________________________________________

4. Предположим, что все остатки различны. Посмотрим на порядки 2 и 3 по модулю . (Порядок по модулю - минимальное натуральное такое, что (или числитель соответствующей несократимой дроби,если - дробь) кратно ; это мы будем обозначать .) По МТФ они могут быть равны лишь . Первые два случая проигнорируем, а случаи, когда хотя бы один из порядков равен , идентичны разобранным в пунктах 1 и 3 . Пусть порядки , в частности все остатки , различны (иначе, если и дают одинаковые остатки, то , а значит и , кратно , но ) и найдётся такое , что . Отметим также, что в этом случае , так что если при некотором имеем , то и , так что нарушается условие различности остатков. Поэтому в нашей последовательности встречаются по разу все ненулевые остатки.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Пусть простое и таково, что для любого число и остаток от деления на имеют разную чётность. Тогда .

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

Доказательство. Действительно, попробуем в качестве все числа от 1 до . Пусть все пары не подошли, т.е. все имеют остатки по модулю , большие . Это значит, что чётность остатка по модулю противоположна четности остатка по модулю ( - нечётно), а она совпадает с четностью (т.к. нечётно), и мы попадаем в условия леммы.

_________________________________________________________________________________________________________________________________________________________________________________

Подберём по следствию 1 такое , что при делении на имеет остаток меньше , назовём этот остаток делится на .

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

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

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