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

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

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

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

a  ≡ 0 (mod  p);

ap  ≡ 0 (mod  p);

или  ap  ≡  a  (mod  p).

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

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

рассмотрим числа  a, 2a,   - 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);

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