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(\mod p)$

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

$a^{p}\equiv a(\mod p)$

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(\mod 11)$ pra

$(7^{10})^{k}\equiv 1(\mod 11)$ 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(\mod 11)$ pra

$7^{222}\mod 11=5$

Këtu përdorum teoremen e vogël së Fermas për të llogaritur $a^{n}\mod p$ 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\leq 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}(\mod p)$ prandaj për të gjetur $a^{n}\mod p$ ne vetëm duhet të llogarisim $a^{r}\mod p$