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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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


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

a^{p-1} \equiv 1 \pmod{p}


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

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


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

Ще докажем, че за всяко просто 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).