Общая теорема Ферма: доказательство

[bayah]

Вероятно эта не та теорема Ферма о которой вы подумали. Простите меня за этот маркетинг).
Собственно тут речь о упражнении из Куранта, Роббинса "Что такое математика".
Скажите верно ли доказательство?

Теорема Ферма выглядит так:

Если $p$ - простое число, не делящее целого числа $a$, то

$a^{p-1}\equiv 1\pmod{p}$

Ее доказывать не нужно, а предлагается доказать общую теорему Фурма (исходя из того, что вышеописанное уже доказано):
наименьшее число $e$, для которого $a^e\equiv 1\pmod p$, должно быть делителем $p-1$.


Можно записать, что

$p-1 =ke + r$, (1)
где $0 \le r<e$

Нужно доказать, что $r=0$, что и будет значить, что $e$ - делитель $p-1$.

Так же по условию:
$a^{p-1}\equiv 1 \pmod{p}$ (2)
$a^e \equiv 1\pmod{p}$ (3)

Подставим (1) в (2):

$a^{ke + r}\equiv 1 \pmod{p}$
$a^{ke} \cdot a^r \equiv 1 \pmod{p}$ (4)

Рассмотрим $a^{ke}$:
- Если $k = 0$, то $a^{ke} = a^{0} = 1 \equiv 1 \pmod p$
- Если $k = 1$, то $a^{ke} = a^{e} \equiv 1 \pmod p$, из условия (3)
- Если $k > 1$, то $a^{ke} = a^{e}\cdot ... \cdot a^{e} \equiv 1 \pmod p$, опять же из условия (3) и свойства произведения сравнений

Из того, что во всех случаях $a^{ke} \equiv 1 \pmod p$ и из равенства (4), следует, что $a^r \equiv 1 \pmod p$
Так как $e$ - наименьшее число, для которого $a^e\equiv 1\pmod p$, и $r<e$, то $a^r \equiv 1 \pmod p$ только в случае $r=0$.

Что и требовалось доказать.

Меня смущает момент, что е - наименьшее число просто по условию. Не нужно ли это доказывать? Или я туплю?)

[Deggial]

bayah в сообщении #938301 писал(а):

Вероятно эта не та теорема Ферма о которой вы подумали. Простите меня за этот маркетинг).

Название темы уточнено.

bayah в сообщении #938301 писал(а):

Меня смущает момент, что е - наименьшее число просто по условию. Не нужно ли это доказывать?

Не нужно: рассматривать можно что угодно.

[bayah]

Спасибо