Fermaten teorema txikia

Fermaten teorema txikia aritmetika modularrarekin lotutako zenbakien teoriako teorema klasikoetako bat da. Hau baliatuz, zatiketa batetik lortzen dugun hondarra kalkulatu daiteke. Honako hau da bere definizioa:

p zenbaki lehena bada, orduan, a zenbaki natural bakoitzerako non a>0 , a^p ≡ a (mod p)

Pierre de Fermat, 1636

Baliokidea den arren, orokorrean teorema beste modu honetan aurkezten da:

p zenbaki lehena bada, orduan, a zenbaki natural bakoitzerako, non a>0 , den eta zkh(p,a)=1 den a^p-1 ≡ 1 (mod p)

Pierre de Fermat, 1636

Horrek esan nahi du a zenbaki bat p-garren potentziara igotzen bada eta emaitza a-ri kentzen bazaio, hondarra p-rekin zatigarria dela (ikus aritmetika modularra).

Era berean, gure zatitzailea ez bada lehena, aritmetikaren oinarrizko teoremak dioen bezala, zenbaki lehenetan deskonposatu dezakegu. Hau da, demagun gure zatitzailea m dela ${\displaystyle m\in Z}$ izanik. m=pq moduan deskonposatu dezakegu ${\displaystyle p,q\in Z}$ izanik. Hortaz, Fermaten teorema txikia honela berridatzi dezakegu:

${\displaystyle a^{(p-1)(q-1)}\equiv 1{\pmod {pq}}}$

Adibide bat jarriko dugu. Demagun, ${\displaystyle 53^{103}}$ren hondarra kalkulatu nahi dugula 39rekin zatitzean. Lehenik eta behin, 53 39rekin zatitzean 14 geratzen zaigu hondar moduan. Orduan, 14 ordezkatuko dugu 53ren tokian. Ondoren, zkh(39,14)=1 denez, Fermaten teorema txikia aplikatu dezakegu:${\displaystyle 14^{38}\equiv 1{\pmod {39}}}$. Behin espresio hau dugula, ${\displaystyle {14^{38}}^{2}14^{27}\equiv x{\pmod {39}}}$ moduan berridatziko dugu. ${\displaystyle {14^{38}}^{2}}$ hori modulu 39rekin laburtu egiten da eta ${\displaystyle 14^{27}\equiv x{\pmod {39}}}$ izango genuen. Orain, gure helburua, espresioa laburtzea da x hori lortzeko. Horretarako, ${\displaystyle {14^{2}}^{13}14\equiv x{\pmod {39}}}$ moduan berridatziko dugu. Ohartu ${\displaystyle {14}^{2}\equiv 1{\pmod {39}}}$ dela. Horregatik, x=14 da. Hau da, ${\displaystyle 53^{103}\equiv 14{\pmod {39}}}$.

Bere interes nagusia lehentasunaren arazoari eta kriptografiari aplikatzea da. Teorema honek ez du zerikusirik Fermaten Azken Kondairazko Teoremarekin, 350 urtez aieru bat besterik ez zena eta azkenean Andrew Wilesek frogatu zuena 1995ean.