Малка теорема на Ферма

от Уикипедия, свободната енциклопедия

Теоремата на Ферма гласи:

Ако a е цяло число ( $a\in\mathbb{Z}$ ) и p e просто число и ако р не дели а, то

$a^p \equiv a \pmod{p}$

[редактиране] Числови примери

4³ − 4 = 60 се дели на 3.
(−3)⁷ − (−3) = −2184 се дели на 7.
2⁹⁷ − 2 = 158456325028528675187087900670 се дели на 97.

[редактиране] Доказателство на теоремата чрез метода на индукцията

Ще докажем, че за всяко просто p и цяло неотрицателно a, $a p - a$ се дели на p като използваме метода на математическата индукция.

1) За a=0, $a p - a = 0$ и и се дели на p

2) Да допуснем, че е твърдението е вярно за a=k. Ще го докажем и за a=k+1.

$a^p-a = (k+1)^p-(k+1) = k^p+1+\sum_{l=1}^{p-1} {p \choose l} k^l - k-1 =$

$= k^p - k + \sum_{l=1}^{p-1}k^l {p \choose l}$

Но $k p - k$ се дели на p по предположение на индукцията. Що се отнася до другото събираемо, то ${p \choose l} = {p! \over l!(p-l)!}$ . За $1 \le l \le p-1$ , числителя на тази дроб се дели на p, а знаменателя - не се дели, следователно, ${p \choose l}$ се дели на $p$ . Следователно цялата сума $k^p - k + \sum_{l=1}^{p-1} {p \choose l}$ се дели на p, което и трябваше да се докаже.

За отрицателни a и нечетни p теоремата се доказва лесно ако приемем, че b=-a. За отрицателни a и p=2, верността на теоремата следва от $a 2 - a = a (a - 1)$ .