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

от Българският сайт за математика

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

[редактиране] Малка теорема на Ферма 

 Тя гласи, че a^p\equiv a(modp), където p е просто число.

Доказателство: Известен факт е, че простото число p дели p \choose k \forall k\le p-1. Ще докажем следната лема x^p+y^p\equiv(x+y)^p(mod p) за просто p. Тя е обаче директно следствие от Нютоновия бином и от горното твърдение. Лесно по индукция се доказва,че \sum_{i=1}^n x_{i}^p\equiv (\sum_{i=1}^n x_{i})^p(mod p). Сега е достатъчно да положим n=a и x_{1}=x_{2}=...=x_{a}=1, с което теоремата е доказана. Когато gcd(a,p)=1,можем да съкратим на a, т.е тогава е изпълнено и сравнението a^{p-1}\equiv 1(mod p)

Взето от „http://matematika.bg/wiki/%D0%9C%D0%B0%D0%BB%D0%BA%D0%B0%D1%82%D0%B0_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0“.