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

(a) По МТФ Следовательно, С помощью последнего сравнения нетрудно посчитать (четыре раза умножить остаток на что

(b) Заметим, что Посчитаем сначала остаток при делении на а потом — при делении на По МТФ но тогда Также по МТФ Отсюда имеем и Из последнего сравнения нетрудно посчитать, что Значит,

Таким образом, число имеет вид и для некоторых целых и То есть что равносильно Видно, что для выполнения равенства необходимо, чтобы давало остаток при делении на Значит, откуда Заметим, что мы нашли остаток при делении на