Литература
Великие математики
Таблицы
Игры
Разное
Гостевая книга
Карта сайта
Формулы сокращенного умножения
Целые числа
Модуль
Делимость. Сравнения
Рациональные уравнения
Рациональные неравенства
Степени. Корни
Тригонометрические уравнения, неравенства
Показательные уравнения, неравенства
Логарифмические уравнения, неравенства
Арифметические, геометрические прогрессии
Комбинаторика. Бином Ньютона
Последовательности и пределы
Олимпиадные задачи
Планиметрия
Стереометрия


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


Доказать что, 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);

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


Назад

Поиск по сайту
Перевод на другие языки
Леонард Эйлер (Швейцария, Россия) (1707 - 1783) был настолько плодовит, что и через 50 с лишним лет после его смерти его труды все еще печатались впервые.
На данный момент в базе присутствует информация о 1847 великих математиках.

Для ознакомления доступны 48 книг.
Если вы хотите оказать помощь проекту - прочтите, пожалуйста, это.
Наш проект в социальных сетях:
- Живой журнал
- Facebook
- Twitter
Чтобы сайт всегда был под рукой:
- Добавить в избранное
Также вы можете добавить новости проекта в свою "Ленту новостей":
- RSS
Свяжитесь с нами используя раздел Контакты
Последняя новость :

Добавлен материал "Показательные уравнения и неравенства", в котором заполнены разделы "Теория" и "Методы решений". В ближайшее время ожидайте задачи по этому материалу.
18.03.2013

Rambler's Top100



2009-2013 © "Математика - это просто!" - некоммерческий, обучающий сайт. Все права принадлежат их владельцам.
При использовании материала ссылка на первоисточник обязательна.
Особая благодарность Артему Субачу за консультации при создании данного проекта.