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 a^p − a estas dividebla per p. Ĉi tio povas esti esprimita en la notacio de modula aritmetiko jene:

a^p ≡ a  (mod p)

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

a^p−1 ≡ 1 (mod p)

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

Ekzemploj

• 4³ − 4 = 60 estas dividebla per 3.
• 7² − 7 = 42 estas dividebla per 2.
• 3⁷ − 3 = 2184 estas dividebla per 7.
• 2⁹⁷ − 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 jeno : 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 $m\equiv n{\pmod {p-1}}\,$, tiam $\forall a\in \mathbb {Z} :\quad a^{m}\equiv a^{n}{\pmod {p}}.$ 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:

$a^{\varphi (n)}\equiv 1{\pmod {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 a^p−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

Eksteraj ligiloj

• Eric W. Weisstein, Malgranda teoremo de Fermat en MathWorld.
• 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 Arkivigite je 2004-10-22 per la retarkivo Wayback Machine