2. Теорема Ферма.
В XVII столетии Ферма, основатель современной теории чисел, открыл чрезвычайно важную теорему. Если 
простое число, не делящее целого числа а, то
Другими словами, 
степень а при делении на 
дает остаток 1.
Некоторые из ранее произведенных нами вычислений подтверждают эту теорему: так, мы видим, что 
. Таким же образом легко проверить, что 
. Для этой цели нет необходимости на самом деле вычислять столь высокие степени данных чисел; достаточно использовать мультипликативное свойство сравнений:
Обращаясь к доказательству теоремы Ферма, рассмотрим числа, кратные а:
Никакие два из этих чисел не могут быть между собой сравнимы по модулю 
В противном случае 
должно было бы делить разность 
где 
была бы пара целых чисел, подчиненных ограничению 
Но из закона 7) следует, что этого не может случиться: так как 
меньше, чем 
то 
не делит 
с другой стороны, по предположению, 
не делит и а. Таким же образом мы убеждаемся, что ни одно из чисел 
не сравнимо с нулем. Отсюда следует, что числа 
соответственно сравнимы с числами 
взятыми в некоторой их перестановке. Дальше заключаем:
или же, полагая ради краткости 
Число К не делится на 
так как ни один из входящих в него множителей не делится на 
значит, согласно закону 
должно делиться на 
т. е.
Это и есть теорема Ферма.
Проверим эту теорему еще раз. Возьмем 
тогда получаем по модулю 
Если возьмем 
вместо 5, то будем иметь, опять-таки по модулю 
. В примере, где было взято 
(как и во многих иных), можно заметить, что не только 
степень, но и более низкая степень а уже оказывается сравнимой с единицей. Наименьшая такая степень — в нашем примере степень 11 — непременно есть делитель числа 
(см. ниже упражнение 3).
Упражнения.
(см. скан)
