Teorema e vogël Fermat

Matematikanti francez Pierre de Fermant bëri shumë zbulime të rëndësishme në teorin e numrave.Një më të dobishme nga këto zbulime është që p pjeston $a^{p-1}p-1$ kurdoher kur p është numër i thjeshtë dhe a është numër i plotë jo i pjestueshum me p.

Teorema e vogël e Fermas

Nëse p është numër i thjesht dhe a numër i plot jo i pjestueshum nga p atëher

$a^{p-1}\equiv 1(modp)$

Për më tepër për gjdo numër të plot a kemi

$a^p\equiv a(modp)$

Teorema e vogël e Fermas na tregon nëse $a\in Z_p$ pastaj $a^{p-1}=1$ në $Z_p$

Teorema e e vogël e Fernas është jashtzakonisht e dobishme në llogaritjen e mbetjeve modulo p të fuqive të mdha të numrave të plotë

Shembuj

$7^{222}mod11$

Nga teorema e vogël e fermas e dim se $7^{10}\equiv 1(mod11)$ pra

$(7^{10}{)}^k\equiv 1(mod11)$ për gjdo numër pozitiv të plotë k

Me zbatimin e ksaj kongruence pjestojm 222 me 10 duke gjetur se $222=22\times 10+2$ atëher kemi

$7^{222}=7^{22\times 10+2}=(7^{10}{)}^{22}{7}^2\equiv (1{)}^{22}\times 49\equiv 5(mod11)$ pra

$7^{222}mod11=5$

Këtu përdorum teoremen e vogël së Fermas për të llogaritur $a^{n}modp$ ku p është numër i thjesht dhe $p\nmid a$ së pari përdorum algoritmin e pjestimit për të gjetur herësin q dhe mbetjen r kur n pjestohet nga p-1, ashtu që $n=q(p-1)+r$ ku $0\le r<p-1$ rrjedh se $a^n=a^{q(p-1)+r}=(a^{p-1}{)}^q{a}^r\equiv 1^q{a}^r\equiv a^r(modp)$ prandaj për të gjetur $a^{n}modp$ ne vetëm duhet të llogarisim $a^{r}modp$