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

Из Википедије, слободне енциклопедије

Мала Фермаова теорема (није исто што и последња Фермаова теорема) тврди да ако је 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.

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

Примери[уреди]

  • 43 − 4 = 60 је дељиво са 3.
  • 72 − 7 = 42 је дељиво са 2.
  • (−3)7 − (−3) = −(2 184) је дељиво са 7.
  • 297 − 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 било који прост број.

Литература[уреди]