Aritmetika modular

Aritmetika modularra, matematikaren esparruan, zenbaki osoko kongruentzia klaseetarako sistema aritmetikoa da. 1801ean Carl Friendrich Gaussek garatu zuen eta Disquisitiones Arithmeticae izeneko liburuan argitara eman zuen.

Erlojuaren aritmetika moduan ere ezagutzen da, orduak 12:00-etara iristean berriro 00:00-tik kontatzen hasten baitira; 12 orduko erlojua aritmetika modularraren adibide argia da. Erloju analogikoetan, eguna 12 orduko bi zatitan banatuta dago; goizeko 7:00-ak badira eta 8 ordu pasa badira, 15:00-ak izan beharko lirateke, baina 0tik 12ra kontatzen duenez, 3:00-ak direla esaten dugu. Modu berean, 12:00-ak badira eta 21 ordu pasa badira, 9:00-ak direla esaten dugu 33:00-ak direla esan beharrean, erlojuaren orratza 12:00-ra iristean berriro ere 0tik kontatzen hasten delako. Hori horrela izanik, erloju analogikoetan 12 moduluko aritmetika egiten dela esango dugu.

Kongruentzia erlazioa 
Aritmetika modularra era matematikoan eraikia izan daiteke zenbaki osoen arteko  moduluko kongruentzia erlazioaren bidez, batuketa, kenketa eta biderketa eragiketekin bateragarria dena. ,  izanik,  moduluko kongruentzia erlazioa honela definitzen da:

a eta b zenbaki osoak kongruenteak dira modulu , (a – b) zenbaki osoa -ren multiploa bada, edo, beste modu batean esanda, -k (a – b) zatitzen badu.

 non , hau da, 

Erlazioa era honetan adierazten da:  

Adibideak:

Kasu honetan argi ikusten da 38 – 14 = 24, 12ren multiploa dela, 12 x 2 = 24 baita.  zenbaki negatiboetarako adibideak:

Hondarrak 
Aritmetika modularra zatiketa Euklidearrarekin erlazionatuta dago. Izan ere, zatiketa Euklidearraren hondarra bilatzearen eragiketari "modulu eragiketa" ere deitu ohi zaio, eta “mod” aurrizkiaren bidez adieri ohi da. Horrela, adibidez, 14 eta 12ren arteko zatiketaren hondarra 14 mod 12 moduan adieraz daiteke. Hondar hori 2 denez, 14 mod 12 = 2 idazten da.

Azken batean a eta b bi zenbaki oso kongruenteak direla modulu  esaten dugunean, zera adierazi nahi dugu:  balioaz zatitzean lortzen den hondarra bietarako berbera dela.

eta

adierazpenak baliokideak dira.

Gogoan izan behar da hondarra beti zenbaki oso positiboa dela.

Adibideak (12 moduluko kongruentziarako eta 5 moduluko kongruentziarako):

. Hondarra 2 da.

. Hondarra 2 da.
. Hondarra 2 da.
. Hondarra 2 da.

Hortaz, 5 moduluko kongruentzian -8, 2, -3 eta 7 kongruenteak dira haien artean; 5 balioaz zatitzean 2-ko hondarra lortu da kasu guztietan.

Hondarraren teorema txinatarra 
Demagun n1,n2,...,nk zenbaki oso eta binaka elkarrekiko lehen ditugula. Orduan, emandako a1,a2,...,ak -entzako existitzen da x zenbaki oso bat kongruentzien sistemaren soluzio bakarra dena  moduluarekiko.

Eta sistemaren x soluzio guztiak   dira.

Fermaten teorema txikia eta Eulerren teorema 
Fermaten teorema txikia erabiltzen da bi moduluak zenbaki lehenak direnean. 

Izan bedi p zenbaki lehena eta edozein a :

Froga:

Har ditzagun a, 2a,... (p-1)a zenbakiak eta ohartu zerrenda horretan ez daudela bi zenbaki p moduluarekiko kongruenteak direnak. Izan ere,  bada, (x-y)a p-ren pultiploa da, baina p lehena denez eta ez duenez a zatitzen, (x-y) zatituko du. Beraz, x-y=0 da,  direlako.

Hartutako bi zenbakiak, p-rekin zatitzean hondar desberdinak ematen dituzte eta ez dago p-ren multiplorik haien artean. Beraz,  edo .Azken formula honetatik, hasierako formulara heltzen gara; izan ere, zki(p,(p-1)!)=1.

Expresio hau orokortu zuen Eulerrek eta ondoko korolarioa enuntziatu zuen: edozein  eta horrekiko lehena den edozein , non  Eulerren phi funtzioa adierazten du, zeinak 1-etik n-rainoko n-rekiko zenbaki lehen oso guztiak kontatzen ditu. Eulerren teorema, Lagrangeren teoremaren ondorio bat da, ℤ/nℤ taldeko eraztuneko unitateen kasuari aplikatuta.

Eragiketak 
Esan bezala, kongruentzia erlazioa, batuketa eta biderketa modularrarekin bateragarria da.

Batuketa modularra 
Baldin eta

eta

orduan

Adibidea:

 eta  izanik,

Ondorioz, batuketa modularra horrela idatz daiteke:

edo, bere baliokidea dena:

Biderketa modularra 

Baldin eta

eta

orduan

Adibidea:

 eta  izanik,

Ondorioz, biderkadura, aritmetika modularraren oinarrizko propietatea dena, horrela idatzia izan beharko litzateke:

edo, bere baliokidea dena:

Berreketa modularra 

,  izanik,  berreketa biderketen bidez kalkulatzean,

x berretzailea handia denean bi arazo mota sortzen dira:

•  handiegia da: kalkulatu nahi izateak arazoak sor ditzake.

• a zenbakia bere buruarekin x − 1 aldiz biderkatu behar da: Biderketa kopuru handia.

Aritmetika modularrean,  kalkulatzean:

• Zenbaki handiegien arazoa ekiditen da, ez dago  kalkulatu beharrik, horrela eragiten delako.

  

• Berreketa bitarraren metodoa. x berretzailearen adierazpen bitarra erabiliz biderketa kopuru minimoa kalkulatuko da.

Alderantzizko modularra 
 multzoko elementu guztiek ez dute alderantzizkorik, ezta  multzoko guztiek alderantzizko modularrik ere.

a elementua alderantzikagarria izateko  beteko
duen  existitu behar da multzoan.

Alderantzizko modularraren existentzia 
 existitzen da baldin eta soilik baldin  bada.

 multzoan alderantzikagarri diren elementuen multzoa  da.

n moduluko hondarren multzo murriztua:

 .

Alderantzizko modularra existitzen denean,  kalkulatzeko Euklidesen algoritmoa erabiltzen da.

Alderantzizko modularraren kalkulua Euklidesen algoritmoa erabiliz 
Izan bitez  lehen erlatiboak, .

Dakigunez,  non .

Hortaz,

 non .

a-ren alderantzizkoa modulu  x dela ondoriozta daiteke horrela:

 

Euklidesen algoritmoa erabiliz x kalkulatzen da, hau da, .

Kongruentzia klaseak 
 moduluko kongruentzia baliokidetasun erlazioa da. a zenbaki osoaren baliokidetasun klasean honako elementuak daude:

[a]={…, a - 2n, a - n, a, a + n, a + 2n,…}

Multzo horretan a elementua dago, eta harekin kongruente modulu  diren gainerako zenbaki oso guztiak ere. Multzoa [a] notazioaz adierazten da eta a-ren kongruentzia klasea dela esaten da.

Aplikazioak 
Aritmetika modularrak zenbait aplikazio ditu, bai zenbaki teorian, bai aljebra abstraktuan, bai kriptografian, baita arte bisual eta musikaletan ere.

Gaur egun konputagailu gehienetan egiten diren eragiketa aritmetikoak modularrak dira, modulua 2b izanik (b = eragiketako balioen bit kopurua). Eragiketa modularrak programazio-lengoaia askotan eta kalkulagailuetan inplementatuta daude. XOR 2 biten batuketa da, modulu 2. "Int"-en gaineko eragiketa aritmetiko guztiak, esaterako, modulu 232 hartzen dira konputagailu gehienetan.

Musikan, 12 moduluko aritmetika erabiltzen da eskala dodekafonikoaren azterketan, non zortzigarrena eta baliokidetasun enarmonikoa produzitzen dituen (hots, 1∶2 edo 2∶1 erlazioak baliokideak dira eta Do# eta Reb bera dira).

Arte bisualetan, aritmetika modularra patroi artistikoak sortzeko erabili daiteke, modulu n biderketa tauletan oinarrituta.

Aritmetika modularra sarritan erabiltzen da identifikatzaileen barnean erabiltzen diren kontrol baturak kalkulatzeko. Esate baterako, Nazioarteko kontu-korronteen zenbakiak (IBAN), modulu 97 eragiketa aritmetikoa erabiltzen du bankuko kontu korronteetan erabiltzaile-sarrera akatsak harrapatzeko.

Kriptografian, aritmetika modularra RSA eta Diffie-Hellman-en zifratze-protokoloa bezalako gako publikoen sistemen oinarria da; kriptografia simetrikoa erabiltzen da, horien artean, zifratze estandar aurreratua (AES-a), datuak zifratzeko nazioarteko algoritmoa (IDEA) eta RC4. RSA-k eta Diffie-Hellman-en zifratze-protokoloak berreketa modularra darabilte.

Ikuspegi orokorrago batetik, aritmetika modularrak beste zenbait aplikazio ditu, bai zuzenbidean, bai ekonomian, baita giza-zientzien beste area batzuetan ere, non zatiketa proportzionalak eta errekurtso-esleipenak analisiaren zati garrantzitsua jokatzen baitute.

Kanpo estekak 

Aritmetika modularra
Talde-teoria
Eraztunen teoria
Matematika diskretua