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