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 redakti
- 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 redakti
Pierre de Fermat donis la teoremon sen pruvo en letero de 18-a de oktobro, 1640 al lia amiko Frénicle de Bessy kiel jeno[1] : 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.
Ĝeneraligoj redakti
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 redakti
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).