C6. Найдите наибольший общий делитель всех чисел вида p2 - 1, где р - простое число, большее 3, но меньшее 2010.
Решение I. Рассмотрим числа вида p2 - 1, где p>3. Самое меньшее из них равно 52 - 1 = 24. Значит, наибольший общий делитель указанных чисел больше 24 быть не может.
Докажем, что 24 - наибольший общий делитель данных чисел. Для этого достаточно доказать, что p2 - 1 делится на 24.
Пусть p = 2k + 1 (четных простых чисел больших 3 нет). Тогда А = p2 - 1 = 2k(2k+2)=4k(k+1).
В произведении чисел k(k+1) обязательно есть чётное число. Поэтому А делится на 8. Осталось показать, что в произведении k(k + 1) делится на 3.
Если предположить, то ни k, ни k + 1 не делятся на 3, то k = 3n + 1 (если k = 3n + 2, то k + 1 = 3n + 3 - делится на 3). Но тогда простое число p = 2k + 1 = 2(3n + 1)+1 = 6n + 3 делится на 3. Чего быть не может. Значит, либо k, либо k + 1 делится на 3.
Таким образом, p2 - 1 делится на 8 и 3. Так как 8 и 3 взаимно простые числа, то p2 - 1 делится и на их произведение 24. Значит, 24 - наибольший общий делитель искомого множества чисел.
Ответ: 24.
Решение II. Каждое натуральное число можно представить в виде 6k или 6k + 1 или 6k + 2 или 6k + 3 или 6k + 4 или 6k + 5. Простое число р ( р > 3) можно представить в виде 6k + 1 или 6k + 5 (остальные числа: 6k, 6k + 2, 6k + 3 и 6k + 4 не являются простыми).
Если р = 6k + 1, то p2 - 1 = (р - 1)(р + 1) = 6k ⋅ (6k + 2) = 12k ⋅ (3k + 1). При этом одно из чисел k и 3k + 1 будет обязательно четным. Это легко проверить рассмотрением двух случаев: k - четное (в этом случае наше утверждение верно) и k - нечетное (в этом случае 3k + 1 - четное). Значит, число 12k ⋅ (3k + 1) делится на 24. Поэтому и 3p2 - 1 делится на 24.
Если р = 6k + 5, то p2 - 1 = (р - 1)(р + 1) = (6k + 4) ⋅ (6k + 6) = 12(3k + 2) ⋅ (k + 1). Как и в предыдущем случае можно доказать, что одно из чисел: 3k + 2 и k + 1 будет четным (представляем читателям это сделать самостоятельно). Значит, 12(3k + 2) ⋅ (k + 1) делится на 24. Из последнего следует, что и p2 - 1 делится на 24.
В предыдущем решении показано, что наибольший общий делитель наших чисел не превосходит 24. Так как все числа вида p2 - 1 делится на 24, то их наибольший общий делитель равен 24.
Ответ: 24.
N. B. Перед публикованием этой заметки я посмотрел в Интернете решения этой задачи. Практические они не отличаются от приведенных выше (или наоборот :). Однако на одном из форумов встретил слова: "Кто хотел использовать в решении условие про 2010, тот обломался" .
Действительно, ни в одном из приведенных выше решений не используется условие, что рассматриваются числа р не превосходящие 2010. Если отбросить в условии задачи это условие, то получим бесконечное множество чисел вида р2 - 1, где р - простое число, большее 3. Понятие же наибольшего общего делителя определено только для конечного множества. Значит, и вся теория использованная мною имеет место для конечного набора целых чисел.
Рассмотренная в этой заметке задача не нова. Я ее встречал в иной формулировке: "Доказать, что любое число вида р2 - 1, где р - простое число, большее 3 делится на 24". Думаю, что эта формулировка удачнее той, которая использована в задании типа С6. В традиционной формулировке отпадает необходимость в рудименте "меньшее 2010" .
Как бы то ни было есть необходимость в обсуждении того, что вся теория о НОД и НОК действует только в мире конечного множества чисел.
C6. Найдите наибольший общий делитель всех чисел вида p2 - 1, где р - простое число, большее 3, но меньшее 2010.
