2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Следствие из теоремы Ферма
Сообщение16.07.2010, 23:02 
Аватара пользователя
Привет,

Я опять с очевидной, по всей видимости задачей.
Требуется доказать следующее утверждение: наименьшее число $e$, для которого $a^e\equiv 1(mod p)$, где $p$ - простое число, не делящее $a$, должно быть делителем $p-1$.
Рассуждения следующие:
Возьмём минимальное $e$ большее 0, для которого $a^e\equiv 1(mod p)$. Это $e$ меньше $p$. Разделим $p-1$ на $e$: $p-1=ke+r$, где $k$ - целое, а $r$ подчиняется следующему неравенству $0\leqslant r < e$.
$a^{p-1} \equiv 1 \equiv a^e \Rightarrow a^{p-1} \equiv a^e \Rightarrow a^{ke+r} \equiv a^e \Rightarrow a^{ke+r}-a^e \equiv 0 \Rightarrow a^e(a^{(k-1)e+r}-1) \equiv 0 \Rightarrow a^{(k-1)e+r}-1 \equiv 0 \Rightarrow a^{(k-1)e+r} \equiv 1$.
Предпоследнее преобразование делается исходя из того, что если ab \equiv 0$, то либо a \equiv 0$ либо b \equiv 0$. В нашем случае a^e \equiv 0$ - неверно по условию.
Проведём вышеописанную операцию k раз и получим $a^{(k-k)e+r} \equiv 1 \Rightarrow a^r \equiv 1$. Однако $e$ - наименьшее число, что $a^e\equiv 1$ и $r<e$. Следовательно $r=0$, то есть $p-1=ke$, что и требовалось доказать.
Скажите, верны ли мои рассуждения? Можно ли доказать это утверждение проще?

 
 
 
 Re: Следствие из теоремы Ферма
Сообщение17.07.2010, 01:52 
Аватара пользователя
ean в сообщении #339575 писал(а):
Можно ли доказать это утверждение проще?

Так как $a^e\equiv 1\pmod{p}$, то $a^{ke+r}\equiv a^{ke}a^r\equiv (a^e)^ka^r\equiv 1^ka^r\equiv a^r\pmod{p}$.

 
 
 
 Re: Следствие из теоремы Ферма
Сообщение19.07.2010, 12:34 
Аватара пользователя
Спасибо.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group