Mala Fermatova teorema

Mala Fermaova teorema (nije isto što i poslednja Fermaova teorema) tvrdi da ako je p prost broj, onda će za svaki ceo broj a, ${\displaystyle (a^{p}-a)}$ biti deljivo sa p. Ovo se može iskazati u notaciji modularne aritmetike na sledeći način:

${\displaystyle a^{p}\equiv a{\pmod {p}}\,\!}$

Postoji i varijanta ove teoreme iskazana na sledeći način: ako je p prost i a je ceo broj uzajamno prost sa p, onda će :${\displaystyle (a^{p-1}-1)}$ biti deljivo sa p. Zapisano u modularnoj aritmetici:

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}\,\!}$

Drugi način da se ovo iskaže je da ako je p prost broj, i a je bilo koji ceo broj koji nije deljiv sa p, onda a na stepen p-1 daje ostatak 1 kada se podeli sa p.

Mala Fermaova teorema je osnova Fermaovog testa za proste brojeve.

• 4³ − 4 = 60 je deljivo sa 3.
• 7² − 7 = 42 je deljivo sa 2.
• (−3)⁷ − (−3) = −(2 184) je deljivo sa 7.
• 2⁹⁷ − 2 = 158 456 325 028 528 675 187 087 900 670 je deljivo sa 97.

Ferma je objasnio ovu teoremu bez dokaza. Prvi koji je dao dokaz je bio Gotfrid Lajbnic, u rukopisu bez datuma, gde je napisao da je znao dokaz pre 1683.

Prosta generalizacija ove teoreme koja direktno sledi iz nje je: ako je p prost broj i ako su m i n pozitivni celi brojevi, i ${\displaystyle m\equiv n{\pmod {p-1}}\,}$, onda ${\displaystyle a^{m}\equiv a^{n}{\pmod {p}}\quad \forall a\in \mathbb {Z} }$. U ovom obliku se teorema koristi da opravda metod enkripcije sa RSA (RSA) javnim ključem.

Malu Fermaovu teoremu je moguće uopštiti pomoću Ojlerove teoreme: za svako modulo n i svaki ceo broj a uzajamno prost sa n, važi

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$

gde φ(n) označava Ojlerovu φ funkciju koja daje broj celih brojeva između 1 i n koji su uzajamno prosti sa n. Ovo je zaista generalizacija, jer ako je n = p prost, onda je φ(p) = p − 1.

Ovo se može dalje uopštiti u Karmajklovu teoremu.

Mala Fermaova teorema ima i uopštenje u konačnim poljima.

Iz male Fermaove teoreme sledi Hanamova lema; (p-2)! = 1 mod p, gde je p bilo koji prost broj.

• Paulo Ribenboim (1995). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. ISBN 0-387-94457-5.
• Janoš Boljaj i pseudoprosti brojevi Arhivirano 2004-10-22 na Wayback Machine-u (na mađarskom)