Обратные остатки

(a) 

_________________________________________________________________________________________________________________________________________________________________________________

Первое решение. Сгруппируем слагаемые и немного преобразуем

Так как — простое, то при приведении к общему знаменателю не сократится. Следовательно, числитель делится на

______________________________________________________________________________________________________________________________________________________

Второе решение. Достаточно показать, что сумма по модулю равна нулю. Заметим, что все обратные остатки не сравнимы по модулю тогда

_________________________________________________________________________________________________________________________________________________________________________________

(b) Приведём дробь к общему знаменателю:

Знаменатель полученной дроби взаимно прост с следовательно, достаточно показать, что числитель делится на

Рассмотрим набор чисел

Покажем, что элементы образуют полную систему вычетов по модулю Предположим противное, тогда найдутся два слагаемых с одинаковым остатком:

Все множители взаимно просты с значит можно сократить: но и — два разных остатка при делении на противоречие. Следовательно, числитель сравним по модулю с суммой всех остатков при делении на кроме

Числитель дроби является суммой квадратов всех чисел из Таким образом,

По формуле суммы квадратов первых натуральных чисел имеем

Наконец, следовательно, взаимно просто с что влечет делимость числителя изначальной дроби на