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, $(a^{p}-a)$ biti deljivo sa p. Ovo se može iskazati u notaciji modularne aritmetike na sledeći način:

$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 :$(a^{p-1}-1)$ biti deljivo sa p. Zapisano u modularnoj aritmetici:

$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.

Primeri

• 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.

Dokaz

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.

Generalizacije

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 $m\equiv n{\pmod {p-1}}\,$, onda $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

$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.

Literatura

• 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)