Докажите общую теорему: наименьшее число 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).]
ВНИМАНИЕ: это упражнение из книги "Что такое математика", и, если вы не понимаете контекста, можете прочесть параграф "теорема Ферма".

Условие:

Доказать, что наименьшее натуральное число , для которого , должно быть делителем ; - простое число, не делящее целого числа .

Пошаговое объяснение:

Пусть число найдено.

Пусть - остаток от деления на , т.е.  

Согласно теореме Ферма .

Но . Значит,

.

При этом, по построению, , откуда, если натуральное, получаем противоречие с тем, что - минимальное из чисел, удовлетворяющих условию. Значит, [учитывая, что из теоремы Ферма следует существование искомого числа] - а это и означает, что - делитель числа .

Ч.т.д.