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:

Txantiloi:TeoremaBaliokidea den arren, orokorrean teorema beste modu honetan aurkezten da:

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 $m\in Z$ izanik. m=pq moduan deskonposatu dezakegu $p,q\in Z$ izanik. Hortaz, Fermaten teorema txikia honela berridatzi dezakegu:

$a^{(p-1)(q-1)}\equiv 1(\mathrm{mod}pq)$

Adibide bat jarriko dugu. Demagun, $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:$14^{38}\equiv 1(\mathrm{mod}39)$. Behin espresio hau dugula, ${14^{38}}^{2}14^{27}\equiv x(\mathrm{mod}39)$ moduan berridatziko dugu. ${14^{38}}^2$ hori modulu 39rekin laburtu egiten da eta $14^{27}\equiv x(\mathrm{mod}39)$ izango genuen. Orain, gure helburua, espresioa laburtzea da x hori lortzeko. Horretarako, ${14^2}^{13}14\equiv x(\mathrm{mod}39)$ moduan berridatziko dugu. Ohartu ${14}^2\equiv 1(\mathrm{mod}39)$ dela. Horregatik, x=14 da. Hau da, $53^{103}\equiv 14(\mathrm{mod}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.

Orokorpenak

Hortik datorren teoremaren orokortze txiki batek honako hau dio: p lehena bada eta m eta n zenbaki oso positiboak badira m ≡ n (mod p-1), orduan am ≡ an (mod p) a zenbaki oso guztietarako. . Honela adierazita, teorema RSA gako publikoaren enkriptatzeko metodoa justifikatzeko erabiltzen da.

Fermaten teorema txikia Eulerren teorema erabiliz orokor daiteke; n edozein modulurako eta n-ko lehen osoko edozeinentzat, honako hau dugu:

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$, non φ (n) n-rekin 1 eta n arteko zenbaki osoen kopurua zenbatzen duen Euler φ funtzioa den.

Hau orokortze bat da, izan ere, n = p zenbaki lehena bada, orduan φ (p) = p - 1. Hala ere, oraindik posible da gehiago orokortzea, Carmichaelen teoreman erakusten den bezala. Lehen bezala, n edozein modulurako eta n duen edozein zenbaki koprimerako, honako hau dugu: {\ displaystyle a ^ {\ lambda (n)} \ equiv 1 {\ pmod {n}}} non orain λ (n) Carmichael funtzioa den.