Какое докозательство малой аксиомы Ферма?
Какое докозательство малой аксиомы Ферма?
Задать свой вопросОсмотрим два варианта: a делится на p; a не делится на p.
1) a делится на p;
Тогда используя сопоставленья запишем:
a 0 (mod p);
ap 0 (mod p);
Либо ap a (mod p).
В этом случае аксиома доказана.
2) a не делится на p;
Осмотрим числа a, 2a, 3a,...,(p - 1)a (*).
Покажем, что эти числа дают разные остатки при делении на p. Явно, остаток также не может быть 0.
Докажем от оборотного.
Пусть какие-то два числа ka, na имеют схожие остатки при дроблении на p (пусть kgt; n). Тогда разность ka - na делится на p. Означает (k - n)a делится на p. Но a не делится на p, а разница k - n меньше p и отлична от нуля, потому также не делится на p. Мы пришли к противоречию - наше предположение, что числа (*) могут давать одинаковые остатки при дробленьи на p ошибочно. Запишем это:
a r1 (mod p);
2a r2 (mod p);
...
(p - 1)a rp - 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);
ap a (mod p);
Что и требовалось доказать.
-
Вопросы ответы
Статьи
Информатика
Статьи
Математика.
Химия.
Русский язык.
Разные вопросы.
Разные вопросы.
Математика.
Русский язык.
Русский язык.
Разные вопросы.
Қазақ тiлi.