Теория чисел на Иннополисе

Заметим, что

Так как числа и взаимно просты, то кратно тогда и только тогда, когда кратно Поскольку — простое, согласно малой теореме Ферма

Рассмотрим все натуральные при которых кратно наименьшее такое обозначим за

Если делится на то

Значит, делится на а значит, и на что и требовалось.

В обратную сторону: если кратно то рассмотрим Воспользуемся алгоритмом Евклида, т.е. свойством НОД

Теперь

Повторяя эти действия, убеждаемся, что в конце получается число

Если не делится на то

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