Изворни код странице Мала Фермаова теорема

'''Мала Фермаова теорема''' (није исто што и [[последња Фермаова теорема]]) тврди да ако је ''-{p}-'' [[прост број]], онда ће за сваки [[цео број]] ''-{a}-'', <math>(a^p - a)</math> бити дељиво са ''-{p}-''. Ово се може исказати у нотацији [[модуларна аритметика|модуларне аритметике]] на следећи начин:
:<math>a^p \equiv a \pmod{p}\,\!</math>

Постоји и варијанта ове теореме исказана на следећи начин: ако је ''-{p}-'' прост и ''-{a}-'' је цео број узајамно прост са ''-{p}-'', онда ће <math>(a^{p-1} - 1)</math> бити дељиво са ''-{p}-''. Записано у модуларној аритметици:
:<math>a^{p-1} \equiv 1 \pmod{p}\,\!</math>

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

Мала [[Пјер де Ферма|Фермаова]] теорема је основа [[Фермаов тест за просте бројеве|Фермаовог теста за просте бројеве]].

== Примери ==
* 4<sup>3</sup> &minus; 4 = 60 је дељиво са 3.
* 7<sup>2</sup> &minus; 7 = 42 је дељиво са 2. 
* (&minus;3)<sup>7</sup> &minus; (&minus;3) = &minus;(2 184) је дељиво са 7.
* 2<sup>97</sup> &minus; 2 = 158 456 325 028 528 675 187 087 900 670 је дељиво са 97.

== Доказ ==
Ферма је објаснио ову теорему '''без''' доказа. Први који је дао доказ је био [[Готфрид Вилхелм Лајбниц|Готфрид Лајбниц]], у рукопису без датума, где је написао да је знао доказ пре [[1683]]. године.

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

Малу Фермаову теорему је могуће уопштити помоћу [[Ојлерова теорема|Ојлерове теореме]]: за свако [[модуларна аритметика|модуло]] ''-{n}-'' и сваки цео број ''-{a}-'' узајамно прост са ''-{n}-'', важи
:<math>a^{\varphi (n)} \equiv 1 \pmod{n}</math>
где &phi;(''-{n}-'') означава [[Ојлерова фи функција|Ојлерову &phi; функцију]] која даје број целих бројева између 1 и ''-{n}-'' који су узајамно прости са ''-{n}-''. Ово је заиста генерализација, јер ако је ''-{n}-'' = ''-{p}-'' прост, онда је -{&phi;(''p'') = ''p'' &minus; 1}-.

Ово се може даље уопштити у [[Карлмајклова функција|Кармајклову теорему]].

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

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

== Литература ==
* -{Paulo Ribenboim (1995). ''The New Book of Prime Number Records'' (3rd ed.). New York: Springer-Verlag. ISBN 0-387-94457-5.}-
* [https://web.archive.org/web/20041022022031/http://bolyai.port5.com/kisfermat.htm Јанош Бољај и псеудопрости бројеви] (на [[мађарски језик|мађарском]])

[[Категорија:Модуларна аритметика]]
[[Категорија:Математичке теореме]]