Question

Какое докозательство малой теоремы Ферма?

Answer 1

Рассмотрим два случая: 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 (пусть k> 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);

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

Answer 2

Доказательство малой теоремы Ферма основано на теории модульной арифметики.

Пусть p - простое число, а a - целое число, не делящееся на p. Тогда малая теорема Ферма утверждает, что a^(p-1) ≡ 1 (mod p).

Для доказательства этого утверждения можно использовать метод математической индукции.

База индукции: Для a = 1 очевидно, что 1^(p-1) = 1 ≡ 1 (mod p).

Шаг индукции: Предположим, что утверждение верно для a = k, то есть k^(p-1) ≡ 1 (mod p). Теперь рассмотрим a = k+1. Мы можем записать (k+1)^(p-1) как сумму биномиальных коэффициентов: (k+1)^(p-1) = C(p-1,0)*k^(p-1) + C(p-1,1)*k^(p-2) + ... + C(p-1,p-2)*k^1 + C(p-1,p-1)*k^0.

Заметим, что каждый из биномиальных коэффициентов C(p-1,i) делится на p для 0 < i < p-1. Таким образом, все слагаемые в сумме, кроме первого и последнего, делятся на p. Поэтому мы получаем: (k+1)^(p-1) ≡ k^(p-1) + 1 (mod p).

Используя предположение индукции k^(p-1) ≡ 1 (mod p), мы получаем: (k+1)^(p-1) ≡ 1 + 1 ≡ 2 (mod p).

Продолжая этот процесс, мы можем увидеть, что (k+1)^(p-1) сравнимо с суммой чисел от 1 до p-1 по модулю p. Поскольку p - простое число, эта сумма равна (p-1)*p/2, что делится на p. Следовательно, (k+1)^(p-1) ≡ 1 (mod p).

Таким образом, мы доказали малую теорему Ферма методом математической индукции.