Question

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

Answer 1

Условие:

Доказать, что наименьшее натуральное число $e$, для которого $a^e\equiv 1\;(mod\; p)$, должно быть делителем $p-1$; $p$ - простое число, не делящее целого числа $a$.

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

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

Пусть $r$ - остаток от деления $p-1$ на $e$, т.е.  

$p-1=ke+r,\;k\in Z,\; 0\leq r <e$

Согласно теореме Ферма $a^{p-1}\equiv1\;(mod\; p)$ .

Но $a^{p-1}=a^{ke}*a^r=\left(a^e\right)^k*a^r\equiv 1^k*a^r\;(mod\; p)=a^r$ . Значит,

$a^r\equiv 1 \; (mod\; p)$.

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

Ч.т.д.