ЛИТЕРАТУРАВЕЛИКИЕ МАТЕМАТИКИТАБЛИЦЫИГРЫРАЗНОЕКОНТАКТЫКАРТА САЙТА
Разделы
?????? ???? ????????? ???????????, ?? ?????? ??????? ??????.
???? ?????? ????????? ???????????

Поиск по сайту
Перевод на другие языки
Последние новости
???????? ???????? "????????????? ????????? ? ???????????", ? ??????? ????????? ??????? "??????" ? "?????? ???????". ? ????????? ????? ???????? ?????? ?? ????? ?????????.
18.03.2013

Прочесть все новости
LiveJournal Vkontakte Facebook Twitter
В избранное Рассылка

Малая теорема Ферма.


Доказать что, apa (mod p), если p - простое.


Доказательство


Рассмотрим два случая: a делится на p; a не делится на p.

1) a делится на p;

Тогда используя сравнения запишем:

a ≡ 0 (mod p);

ap ≡ 0 (mod p);

Или apa (mod p).

В этом случае теорема доказана.

2) a не делится на p;

Рассмотрим числа a, 2a, 3a,...,(p - 1)a (*).

Покажем, что эти числа дают разные остатки при делении на p. Очевидно, остаток также не может быть 0.

Докажем от обратного.

Пусть какие-то два числа ka, na имеют одинаковые остатки при делении на p (пусть k > n). Тогда разность ka - na делится на p. Значит (k - n)a делится на p. Но a не делится на p, а разница k - n меньше p и отлична от нуля, потому также не делится на p. Мы пришли к противоречию - наше предположение, что числа (*) могут давать одинаковые остатки при делении на p ошибочно. Запишем это:

ar1 (mod p);

2ar2 (mod p);

...

(p - 1)arp - 1 (mod p);

Используя свойства сравнения перемножаем предыдущие сравнения. Так как всего множителей p - 1, а все остатки при делении на p разные, то справа будет (p - 1)!

ap - 1(p - 1)! ≡ (p - 1)! (mod p);

(ap - 1 - 1)(p - 1)! ≡ 0 (mod p);

Но (p - 1)! не делится на p, так как p - простое, а все множители факториала меньше p. Значит (ap - 1 - 1) делится на p.

(ap - 1 - 1) ≡ 0 (mod p);

ap - 1 ≡ 1 (mod p);

apa (mod p);

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


Назад


2009-2012 © Все права защищены. "Математика - это просто!" - некоммерческий, обучающий сайт. Все права принадлежат их владельцам.
Rambler's Top100 Украинский портАл