Малая теорема Ферма

Первое решение. Без ограничения общности будем считать, что взаимно просты, по малой теореме Ферма

а значит существует некоторый остаток

такой, что и

В силу того, что либо либо и тогда При этом

Если можно взять два последовательных натуральных числа числа и У числа — наибольший простой делитель а у числа наибольший простой делитель равен ( — наибольшие простые делители, иначе бы числа были бы больше соответственно).

Если же то возьмем последовательные натуральные числа Тогда у числа

— опять-таки наибольший простой делитель, а у числа

наибольший простой делитель равен иначе бы

то есть что не выполняется.

Следовательно, существуют такие два последовательных натуральных числа, что у одного из них наибольший простой делитель равен а у другого —

______________________________________________________________________________________________________________________________________________________

Второе решение. Пусть По китайской теореме об остатках существует такое что и

Число делится на и поскольку у него не может быть простого делителя больше значит, — наибольший простой делитель

Число делится на Если бы у него был больший простой делитель то

Тогда

Рассмотрим теперь числа и Первое делится на второе — на

Число так как поэтому — наибольший простой делитель.

Число поэтому — наибольший простой делитель.

Значит, мы нашли нужную пару чисел.