Malgranda teoremo de Fermat

En nombroteorio, malgranda teoremo de Fermat estas teoremo de se p estas primo, de por ĉiu entjero a, a^p − a estas dividebla per p. Ĉi tiu povas esti esprimita en la skribmaniero de modula aritmetiko kiel:

a^p ≡ a (mod p)

Varianto de ĉi tiu teoremo havas jenan formon: se p estas primo kaj a estas entjero interprima al p, do a^p−1 − 1 estas dividebla per p. En la skribmaniero de modula aritmetiko:

a^p−1 ≡ 1 (mod p)

Malgranda teoremo de Fermat estas bazo por la primeca provo de Fermat.

Ekzemploj[redakti | redakti fonton]

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[redakti | redakti fonton]

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 interprimo al 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[redakti | redakti fonton]

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 RSA publikan ŝlosilan ĉifradan manieron.

Malgranda teoremo de Fermat estas ĝeneraligita per eŭlera teoremo: por ĉiu modulo n kaj ĉiu entjero a interprimo al 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 interprimoj al 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 | redakti fonton]

Se a kaj p estas interprimaj nombroj tia 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 interprima al p estas nombro de Carmichael (ekzemple 561).