Докажите общую теорему: наименьшее число e, для которого a e ≡ 1
(mod p), должно быть делителем p − 1. [Указание: произведите деление p − 1
на e, получая
p − 1 = ke + r,
где 0 6 r < e, и дальше воспользуйтесь тем обстоятельством, что a
p−1 ≡ a
e ≡ 1
(mod p).]
ВНИМАНИЕ: это упражнение из книги "Что такое математика", и, если вы не понимаете контекста, можете прочесть параграф "теорема Ферма".
Условие:
Доказать, что наименьшее натуральное число
, для которого
, должно быть делителем
;
- простое число, не делящее целого числа
.
Пошаговое объяснение:
Пусть число
найдено.
Пусть
- остаток от деления
на
, т.е.
Согласно теореме Ферма
.
Но
. Значит,
При этом, по построению,
, откуда, если
натуральное, получаем противоречие с тем, что
- минимальное из чисел, удовлетворяющих условию. Значит, [учитывая, что из теоремы Ферма следует существование искомого числа]
- а это и означает, что
- делитель числа
.
Ч.т.д.