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

(a) Поделим все числа на и получим последовательных натуральных чисел, среди которых, очевидно, найдётся число, кратное

(b) В прошлом пункте мы поняли, что в последовательности есть член, кратный Следовательно, произведение всех чисел также кратно Тогда в качестве можно взять тот самый член, который делится на

(c) Ясно, что нужно взять тот единственный член, который делится на в противном случае выражение не поделится даже на

Обозначим числа следующим образом: Пусть кратно Следовательно,

Первая скобка делится на Покажем, что то же самое можно сказать про вторую. Заметим, что произведение представляет из себя произведение всех остатков при делении на кроме Значит, оно сравнимо с по модулю Также подметим, что МТФ позволяет заменить на Следовательно, вторая скобка сравнима с по модулю По теореме Вильсона это выражение кратно что и требовалось.