Fermā mazā teorēma

Vikipēdijas lapa
Jump to navigation Jump to search

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 ap-1-1 dalās ar p. Izmantojot modulāro aritmētiku, to var pierakstīt šādi:

Piemēram, ja a=2, bet p=7, tad ap-1-1 = 26-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.[1] 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.[1]

Pierādījums[labot šo sadaļu | labot pirmkodu]

Šeit dotais pierādījums, ko atklāja Džeimss Aivorijs,[2] un atkārtoti atklāja Dirihlē,[3] 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 (ij, i<p, j<p; nezaudējot vispārību var pieņemt, ka i>j), ka

No šī var secināt, ja , 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 ij. 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

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

kas arī bija jāpierāda.

Vispārinājumi[labot šo sadaļu | labot pirmkodu]

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ā

kur 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 .

Pseidopirmskaitļi[labot šo sadaļu | labot pirmkodu]

Ja a un p ir savstarpēji pirmskaitļi un ap-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 skalitlis ir 561. Kārmaikla skaitļu esamība ir iemesls, kāpēc nav spēkā apgrieztā Fermā mazā teorēma.

Pielietojums[labot šo sadaļu | labot pirmkodu]

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.[4]

Atsauces[labot šo sadaļu | labot pirmkodu]

  1. 1,0 1,1 David M. Burton. «The History of Mathematics / An Introduction» (7th izd.). McGraw-Hill, 2011. ISBN 978-0-07-338315-6.
  2. Ivory, James (1806), "Demonstration of a theorem respecting prime numbers", New series of The Mathematical Depository 1 (II): 6–8
  3. Lejeune Dirichlet, Peter Gustav (1828), "Démonstrations nouvelles de quelques théorèmes relatifs aux nombres", Journal für die reine und angewandte Mathematik 3: 390–393
  4. Сагалович Ю. Л. Введение в алгебраические коды — 3-е изд., перераб. и доп. — М.: ИППИ РАН, 2014. — 310 с. — ISBN 978-5-901158-24-1