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.

Erloju horrek 12 moduluko aritmetika erabiltzen du.

Kongruentzia erlazioaAldatu

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  , (ab) zenbaki osoa  -ren multiploa bada, edo, beste modu batean esanda,  -k (ab) 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:

 


HondarrakAldatu

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.

EragiketakAldatu

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


Batuketa modularraAldatu

Baldin eta

 

eta

 

orduan

 

 

Adibidea:

  eta   izanik,

 

Ondorioz, batuketa modularra horrela idatz daiteke:

 

edo, bere baliokidea dena:

 


Biderketa modularraAldatu

Baldin eta

 

eta

 

orduan

 

Adibidea:

  eta   izanik,

 

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

 

edo, bere baliokidea dena:

 


Berreketa modularraAldatu

 ,   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 modularraAldatu

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

a elementua alderantzikagarria izateko   beteko duen   existitu behar da multzoan.


Alderantzizko modularraren existentziaAldatu

  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 erabilizAldatu

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 klaseakAldatu

  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.


AplikazioakAldatu

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 estekakAldatu