Fermā mazā teorēma

Fermā mazā teorēma ir teorēma skaitļu teorijā. Tā apgalvo: ja p ir pirmskaitlis un a ir vesels skaitlis, kas nedalās ar p, tad a^p-1-1 dalās ar p. Izmantojot modulāro aritmētiku, to var pierakstīt šādi:

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

Piemēram, ja a=2, bet p=7, tad a^p-1-1 = 2⁶-1 = 63, kas tiešām dalās ar 7.

Fermā teorēma ir viena no fundamentālajām skaitļu teorijas teorēmām. Tā ir nosaukta par godu Pjēram Fermā, kas 1640. gadā formulēja šo teorēmu. To sauc par "mazo teorēmu", lai atšķirtu no Fermā lielās teorēmas. Pirmais šīs teorēmas pierādījums tika publicēts 1736. gadā un to bija sastādījis Leonards Eilers, tomēr ir zināms, ka Gotfrīds Leibnics nepublicētā manuskriptā bija sniedzis identisku pierādījumu jau pirms 1683. gada.

Pierādījums

Šeit dotais pierādījums, ko atklāja Džeimss Aivorijs, un atkārtoti atklāja Dirihlē, izmanto modulāro aritmētiku.

Aplūkosim visus dažādos nenulles atlikumus, ko var iegūt, skaitli dalot ar p. Tie veido kopu {1, 2, 3, ..., p-1}. Katru šīs kopas locekli reizinot ar a, iegūst kopu {a, 2a, 3a, ..., (p-1)a}. Pierādīsim, ka visi skaitļi iegūtajā kopā ir atšķirīgi pēc moduļa p.

Pieņem pretējo — var atrast tādus skaitļus i un j (i≠j, i<p, j<p; nezaudējot vispārību var pieņemt, ka i>j), ka $i*a\equiv j*a(\mathrm{mod}p).$

No šī var secināt, ja $(i-j)*a\equiv 0(\mathrm{mod}p).$, tātad (i-j)*a dalās ar p. No dotā ir zināms, ka a nedalās ar p. Tātad i-j dalās ar p. Tomēr tas nav iespējams, jo i<p, j<p, tātad i-j<p, turklāt i-j≠0, jo i≠j. Iegūta pretruna, tātad visi skaitļi kopā {a, 2a, 3a, ..., (p-1)a} ir dažādi pēc moduļa p.

Tā kā pēc moduļa p ir iespējami tikai p-1 dažādi atlikumi, tad var izdarīt secinājumu, ka kopa {a, 2a, 3a, ..., (p-1)a} pēc moduļa p ir kopas {1, 2, 3, ..., p-1} permutācija. No šī mēs varam iegūt, ka

$a*2a*3a*...*(p-1)a\equiv 1*2*3*...*(p-1)(\mathrm{mod}p).$

$(p-1)!*a^{p-1}\equiv (p-1)!(\mathrm{mod}p)$

Tā kā (p-1)! nedalās ar p, tad abas dotās vienādības puses var izdalīt ar to, iegūstot

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

kas arī bija jāpierāda.

Vispārinājumi

Eilera teorēma ir Fermā mazās teorēmas vispārinājums. Tā apgalvo, ka katram veselam skaitlim a, kas ir savstarpējs pirmskaitlis ar moduli n ir spēkā

$a^{\phi (n)}\equiv 1(\mathrm{mod}n),$

kur $\phi (n)$ ir Eilera funkcija — naturālo skaitļu skaits, kas nepārsniedz n un ir savstarpēji pirmskaitļi ar n. Fermā mazā teorēma ir Eilera teorēmas speciālgadījums, jo, ja p ir pirmskaitlis, tad $\phi (p)=p-1$.

Pseidopirmskaitļi

Ja a un p ir savstarpēji pirmskaitļi un a^p-1-1 dalās ar p, tas nenozīmē, ka p ir pirmskaitlis. Ja tas nav pirmskaitlis, tad to sauc par Fermā pseidopirmskaitli ar bāzi a. Piemēram, 341 ir Fermā pseidopirmskaitlis ar bāzi 2.

Ja skaitlis p ir Fermā pseidopirmskaitlis ar bāzi a jebkuram a, kas ir savstarpējs pirmskaitlis ar p, bet tas nav pirmskaitlis, tad p sauc par Kārmaikla skaitli. Mazākais Kārmaikla skaitlis ir 561. Kārmaikla skaitļu esamība ir iemesls, kāpēc nav spēkā apgrieztā Fermā mazā teorēma.

Pielietojums

Fermā mazā teorēma ir viena no svarīgākajām skaitļu teorijas teorēmām un tā tiek izmantota arī citās jomās. Tā nozīmīga teorēma kriptogrāfijas jomā, jo tā ir radījusi vairākas tehnikas pirmskaitļu pārbaudei. Tā tiek izmantota RSA šifrēšanas algoritma pareizības pārbaudīšanai.