Edukira joan

Aritmetika modular

Wikipedia, Entziklopedia askea

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 erlazioa

[aldatu | aldatu iturburu kodea]

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:


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

[aldatu | aldatu iturburu kodea]

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

[aldatu | aldatu iturburu kodea]

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.

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


Batuketa modularra

[aldatu | aldatu iturburu kodea]

Baldin eta

eta

orduan

Adibidea:

eta izanik,

Ondorioz, batuketa modularra horrela idatz daiteke:

edo, bere baliokidea dena:


Biderketa modularra

[aldatu | aldatu iturburu kodea]

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

[aldatu | aldatu iturburu kodea]

, 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

[aldatu | aldatu iturburu kodea]

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

[aldatu | aldatu iturburu kodea]

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

[aldatu | aldatu iturburu kodea]

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

[aldatu | aldatu iturburu kodea]

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.


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

[aldatu | aldatu iturburu kodea]