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 ${\displaystyle 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.^[1]

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

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

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

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

Teorema e vogël e Fermas na tregon nëse ${\displaystyle a\in Z_{p}}$ pastaj ${\displaystyle a^{p-1}=1}$ në ${\displaystyle 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ë

${\displaystyle 7^{222}mod11}$

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

${\displaystyle (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 ${\displaystyle 222=22\times 10+2}$ atëher kemi

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

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

Këtu përdorum teoremen e vogël së Fermas për të llogaritur ${\displaystyle a^{n}\mod p}$ ku p është numër i thjesht dhe ${\displaystyle 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ë ${\displaystyle n=q(p-1)+r}$ ku ${\displaystyle 0\leq r<p-1}$ rrjedh se ${\displaystyle 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 ${\displaystyle a^{n}\mod p}$ ne vetëm duhet të llogarisim ${\displaystyle a^{r}\mod p}$

1. ^ Rosen, Kenneth H. (2012). Discrete Mathematics and ItsApplications. New York: McGraw-Hill. fq. 303. ISBN 978-0-07-338309-5. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)