logo search
Коды и шифры

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

Вот несколько элементарных упражнений.

Каков будет остаток, если

  1. 24 разделить на 5?

  2. 34 разделить на 5?

  3. 36 разделить на 7?

  4. 56 разделить на 7?

  5. 310 разделить на 11?

  6. 810 разделить на 11?

  7. 5996 разделить на 97?

Решения

  1. 24=16=35+1. Остаток равен 1.

  2. 34=81=165+1. Остаток равен 1.

  3. 36=729=1047+1. Остаток равен 1.

  4. 56=15625=22327+1. Остаток равен 1.

  5. 310=59049=536811+1. Остаток равен 1.

  6.  В данном случае можно избежать вычислений с большими числами, если использовать модульную арифметику, как описано в главе 1:

8=23,

поэтому

810=230=(25)6=326.

Поскольку

32-1(mod 11),

то

326(-1)6=1(mod 11),

и следовательно, остаток равен 1.

(7) Остаток снова равен 1. Поскольку 5996 - это очень большое число, запись которого состоит из 171 цифры, то использование модульной арифметики здесь просто необходимо. В деталях метод подсчета можно найти в M22.

Всегда ли остаток равен 1, когда слева показатель степени на единицу меньше значения модуля справа? Нет, это не так. Рассмотрим выражение

214=16384=109215+4.

В данном случае остаток равен 4, а не 1. Почему это так? Ответ заключается в том, что 15=35, то есть это число не является простым. Малая теорема Ферма справедлива только для случая, когда модуль - простое число, такое как 5,7,11 или 97, как в приведенных выше примерах. Эйлер показал, как изменится формулировка теоремы, если модуль не является простым. В своем первоначальном виде теорема формулируется так:

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

Если p - простое число, а m - любое число, которое не делится на p, то

mp-11(mod p),

то есть число mp-1 при делении на p дает остаток 1.

Доказательство этой теоремы совсем несложное, и его довольно легко обобщить, чтобы получить доказательство теоремы Ферма-Эйлера (оно приведено в М23).

Обобщение, сформулированное и доказанное Эйлером, справедливо для любого модуля, но в системе RSA используется частный случай, когда модуль является произведением только двух различных простых чисел. Поэтому стоит привести формулировку теоремы для этого случая: