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

Шаблон:Без източници Теоремата на Ферма гласи:

Числови примери

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

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

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

1) За a=1, $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}(\genfrac{}{}{0ex}{}{p}{l})k^l-k-1=$

$=k^p-k+\sum _{l=1}^{p-1}{k}^l(\genfrac{}{}{0ex}{}{p}{l})$

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

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