Malgranda teoremo de Fermat

En nombroteorio, malgranda teoremo de Fermat estas la teoremo, kiu konstatas, ke por ĉiu primo p kaj por ĉiu entjero a, la nombro ap − a estas dividebla per p. Ĉi tio povas esti esprimita en la notacio de modula aritmetiko jene:

ap ≡ a  (mod p)

Varianto de ĉi tiu teoremo havas jenan formon: se p estas primo kaj a estas entjero reciproke prima kun p, tiam ap−1 − 1 estas dividebla per p. En la notacio de modula aritmetiko:

ap−1 ≡ 1 (mod p)

Malgranda teoremo de Fermat estas bazo por la primeco-testo de Fermat.

 Ekzemploj 
 43 − 4 = 60 estas dividebla per 3.
 72 − 7 = 42 estas dividebla per 2.
 37 − 3 = 2184 estas dividebla per 7.
 297 − 2 = 158 456 325 028 528 675 187 087 900 670 estas dividebla per 97.

 Historio kaj pruvoj 
Pierre de Fermat donis la teoremon sen pruvo en letero de 18-a de oktobro, 1640 al lia amiko Frénicle de Bessy kiel jenoTeksto kaj angla traduko de letero de Fermat al Frénicle de Bessy : p dividas na a(p−1) − 1 ĉiam se p estas primo kaj a estas reciproke prima kun p.

Fermat nur skribis ke: Kaj ĉi tiu propozicio estas ĝenerale vera por ĉiuj progresioj kaj por ĉiuj primoj; la pruvo de kiu mi devus sendi al ci, se mi ne timus esti longa.

La unua donita pruvo estas de Gottfried Wilhelm Leibniz en manuskripto sen dato, kie li skribis ankaŭ ke li sciis pruvon antaŭ 1683.

Eŭlero unua publikigis pruvon en 1736 en papero Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio.

Vidu en pruvoj de malgranda teoremo de Fermat.

 Ĝeneraligoj 
Unu ĝeneraligo de la teoremo, kiu senpere sekvas de ĝi, estas sekva: se p estas primo kaj m kaj n estas pozitivaj entjeroj tiaj ke , tiam  En ĉi tiu formo la teoremo estas uzata por pravigi la metodon RSA por publika ŝlosila ĉifrado.

Malgranda teoremo de Fermat estas ĝeneraligita per eŭlera teoremo: por ĉiu modulo n kaj ĉiu entjero a reciproke prima kun n:

kie φ(n) estas la eŭlera φ funkcio kiu estas kvanto de entjeroj inter 1 kaj n, kiuj estas reciproke primaj kun n. Ĉi tio estas ĝeneraligo, ĉar se n = p estas primo, tiam φ(p) = p − 1.

Ĉi tiu povas esti plu ĝeneraligita al funkcio de Carmichael (teoremo de Carmichael).

La teoremo havas ĝeneraligon ankaŭ en finiaj kampoj.

 Pseŭdoprimoj 
Se a kaj p estas reciproke primaj nombroj tiaj, ke ap−1 − 1 estas dividebla per p, tiam p ne nepre estas primo. Se p ne estas primo, tiam p estas pseŭdoprimo al bazo a.

Nombro p kiu estas pseŭdoprimo al bazo a por ĉiu nombro a reciproke prima kun p estas nombro de Carmichael (ekzemple 561).

 Vidu ankaŭ 
 Frakcioj kun primaj denominatoroj
 RSA

 Referencoj 

 Eksteraj ligiloj 


 Malgranda teoremo de Fermat je tranĉi-la-nodon
 Eŭleraj funkcio kaj teoremo je tranĉi-la-nodon
 Malgranda teoremo de Fermat kaj pruvo de Sophie
 János Bolyai kaj la pseŭdoprimoj 

Kategorio:Modula aritmetiko
Kategorio:Matematikaj teoremoj