Задача:
Найдите наибольшее натуральное число n такое, что сумма квадратов любых n простых чисел, больших 3, делится на n.
Решение:
Любое простое число, большее 3, можно представить либо в виде 6n+1, либо в виде 6n–1. Заметим, что (6n±1)2 = 36n2±12n+1 = 24n2+12n(n±1)+1. Заметим, что первые два слагаемых последней суммы делятся на 12 (так как произведение n(n±1) четно). Поэтому квадрат любого простого числа, большего 3, дает при делении на 24 остаток 1. Поэтому сумма 24 таких квадратов всегда делится на 24. С другой стороны, если в наборе из n простых чисел есть пятерка, и мы заменим ее семеркой, сумма квадратов этих чисел увеличится на 24. Поэтому все искомые n должны быть делителями числа 24, откуда и вытекает ответ.
