2014 dxdy logo

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

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




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

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

Если $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$.

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

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

 
 
 
 Re: Малая теорема Ферма: доказательство
Сообщение30.11.2014, 14:15 
Аватара пользователя
 i 
bayah в сообщении #938301 писал(а):
Вероятно эта не та теорема Ферма о которой вы подумали. Простите меня за этот маркетинг).
Название темы уточнено.

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

 
 
 
 Re: Общая теорема Ферма: доказательство
Сообщение03.12.2014, 10:13 
Спасибо

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


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