Мала Фермаова теорема

Мала Фермаова теорема (није исто што и последња Фермаова теорема) тврди да ако је p прост број, онда ће за сваки цео број a, $(a^{p}-a)$ бити дељиво са p. Ово се може исказати у нотацији модуларне аритметике на следећи начин:

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

Постоји и варијанта ове теореме исказана на следећи начин: ако је p прост и a је цео број узајамно прост са p, онда ће $(a^{p-1}-1)$ бити дељиво са p. Записано у модуларној аритметици:

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

Други начин да се ово искаже је да ако је p прост број, и a је било који цео број који није дељив са p, онда a на степен p-1 даје остатак 1 када се подели са p.

Мала Фермаова теорема је основа Фермаовог теста за просте бројеве.

Примери

• 4³ − 4 = 60 је дељиво са 3.
• 7² − 7 = 42 је дељиво са 2.
• (−3)⁷ − (−3) = −(2 184) је дељиво са 7.
• 2⁹⁷ − 2 = 158 456 325 028 528 675 187 087 900 670 је дељиво са 97.

Доказ

Ферма је објаснио ову теорему без доказа. Први који је дао доказ је био Готфрид Лајбниц, у рукопису без датума, где је написао да је знао доказ пре 1683. године.

Генерализације

Проста генерализација ове теореме која директно следи из ње је: ако је p прост број и ако су m и n позитивни цели бројеви, и $m\equiv n{\pmod {p-1}}\,$, онда $a^{m}\equiv a^{n}{\pmod {p}}\quad \forall a\in \mathbb {Z}$. У овом облику се теорема користи да оправда метод енкрипције са РСА (RSA) јавним кључем.

Малу Фермаову теорему је могуће уопштити помоћу Ојлерове теореме: за свако модуло n и сваки цео број a узајамно прост са n, важи

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

где φ(n) означава Ојлерову φ функцију која даје број целих бројева између 1 и n који су узајамно прости са n. Ово је заиста генерализација, јер ако је n = p прост, онда је φ(p) = p − 1.

Ово се може даље уопштити у Кармајклову теорему.

Мала Фермаова теорема има и уопштење у коначним пољима.

Из мале Фермаове теореме следи Ханамова лема; (p-2)! ≡ 1 mod p, где је p било који прост број.

Литература

• Paulo Ribenboim (1995). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. ISBN 978-0-387-94457-9.
• Јанош Бољај и псеудопрости бројеви (на мађарском)