Преглед на кода на Малка теорема на Ферма

{{без източници}}
'''Теоремата на [[Пиер дьо Ферма|Ферма]]''' гласи:

{{дефиниция|
Ако ''a'' е [[цяло число]] (<math>a\in\mathbb{Z}</math>) и ''p'' e [[просто число]], то
: <math>a^{p} \equiv a \pmod{p}</math>
}}

=== Числови примери ===
* 4<sup>3</sup> − 4 = 60 се дели на 3.
* (−3)<sup>7</sup> − (−3) = −2184 се дели на 7.
* 2<sup>97</sup> − 2 = 158456325028528675187087900670 се дели на 97.

=== Доказателство на теоремата чрез метода на индукцията ===
Ще докажем, че за всяко просто ''p'' и цяло неотрицателно ''a'', <math>a^p-a</math> се дели на ''p'' като използваме метода на математическата индукция.

1) За ''a=1'', <math>a^p-a = 0</math> и се дели на ''p''

2) Да допуснем, че твърдението е вярно за ''a=k''. Ще го докажем и за ''a=k+1''.
:<math> a^p-a = (k+1)^p-(k+1) = k^p+1+\sum_{l=1}^{p-1} {p \choose l} k^l - k-1 = </math>
:<math> = k^p - k + \sum_{l=1}^{p-1}k^l {p \choose l}</math>

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

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

[[Категория:Теореми|Ферма малка]]
[[Категория:Теория на числата]]