Пусть . Понятно, что . Пусть существует натуральное , которое делит и , и . Выберем наибольшее из таких чисел. Тогда делит и разность этих чисел, то есть , но , поскольку и взаимно простые числа. Тогда . Итак, делит и , значит, делит . Следовательно, .
В таком случае, . Понятно, что . Раз , то . Теперь совсем просто: , откуда , что также подходит.
Если указанного значения не существует, то . Но тогда , откуда , что не является простым числом.
Пусть
. Понятно, что
. Пусть существует натуральное
, которое делит и
, и
. Выберем наибольшее из таких чисел. Тогда
делит и разность этих чисел, то есть
, но
, поскольку
и
взаимно простые числа. Тогда
. Итак,
делит
и
, значит, делит
. Следовательно,
.
В таком случае,
. Понятно, что
. Раз
, то
. Теперь совсем просто:
, откуда
, что также подходит.
Если указанного значения
не существует, то
. Но тогда
, откуда
, что не является простым числом.