Mala Fermaova teorema

Izvor: Wikipedia

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[uredi - уреди]

  • 43 − 4 = 60 je deljivo sa 3.
  • 72 − 7 = 42 je deljivo sa 2.
  • (−3)7 − (−3) = −(2 184) je deljivo sa 7.
  • 297 − 2 = 158 456 325 028 528 675 187 087 900 670 je deljivo sa 97.

Dokaz[uredi - уреди]

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[uredi - уреди]

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[uredi - уреди]