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 ${\displaystyle n}$ moduluko kongruentzia erlazioaren bidez, batuketa, kenketa eta biderketa eragiketekin bateragarria dena. ${\displaystyle n\in \mathbb {Z} }$, ${\displaystyle \quad n>1}$ izanik, ${\displaystyle n}$ moduluko kongruentzia erlazioa honela definitzen da:

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

${\displaystyle \exists k\in \mathbb {Z} }$ non ${\displaystyle a-b=k\cdot n}$, hau da, ${\displaystyle a=b+k\cdot n}$

Erlazioa era honetan adierazten da: ${\displaystyle a,b\in \mathbb {Z} }$ ${\displaystyle a\equiv b{\pmod {n}}}$

Adibideak:

${\displaystyle 38\equiv 14{\pmod {12}},\quad 12\;|\;(38-14),\quad \exists k\in \mathbb {Z} \quad non\quad 38-14=k\cdot 12,\quad 24=k\cdot 12\Rightarrow k=2\in \mathbb {Z} }$

Kasu honetan argi ikusten da 38 – 14 = 24, 12ren multiploa dela, 12 x 2 = 24 baita. ${\displaystyle a,b\in \mathbb {Z} }$ zenbaki negatiboetarako adibideak:

${\displaystyle {\begin{aligned}-8&\equiv 7{\pmod {5}},\quad 5\;|(-8-7),\quad \exists k\in \mathbb {Z} \quad non\quad -8-7=5\cdot k,\quad -15=5\cdot k\Rightarrow k=-3\in \mathbb {Z} \\[1ex]2&\equiv -3{\pmod {5}},\quad 5\;|(2-(-3)),\quad \exists k\in \mathbb {Z} \quad non\quad 2-(-3)=5\cdot k,\quad 5=5\cdot k\Rightarrow k=1\in \mathbb {Z} \\[1ex]-3&\equiv -8{\pmod {5}},\quad 5\;|(-3-(-8)),\quad \exists k\in \mathbb {Z} \quad non\quad -3-(-8)=5\cdot k,\quad 5=5\cdot k\Rightarrow k=1\in \mathbb {Z} .\end{aligned}}}$

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 ${\displaystyle n}$ esaten dugunean, zera adierazi nahi dugu: ${\displaystyle n}$ balioaz zatitzean lortzen den hondarra bietarako berbera dela.

${\displaystyle a\equiv b{\pmod {n}}}$

eta

${\displaystyle a{\pmod {n}}=b{\pmod {n}}}$

adierazpenak baliokideak dira.

Gogoan izan behar da hondarra beti zenbaki oso positiboa dela.

Adibideak (12 moduluko kongruentziarako eta 5 moduluko kongruentziarako):

${\displaystyle 38\equiv 14{\pmod {12}},\quad 38=12\cdot 3+2,\quad 14=12\cdot 1+2}$. Hondarra 2 da.

${\displaystyle -8\equiv 7{\pmod {5}},\quad -8=5\cdot (-2)+2,\quad 7=5\cdot 1+2}$. Hondarra 2 da. ${\displaystyle 2\equiv -3{\pmod {5}},\quad 2=5\cdot 0+2,\quad -3=5\cdot (-1)+2}$. Hondarra 2 da. ${\displaystyle -3\equiv -8{\pmod {5}},\quad -3=5\cdot (-1)+2,\quad -8=5\cdot (-2)+2}$. 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 n₁,n₂,...,n_k zenbaki oso eta binaka elkarrekiko lehen ditugula. Orduan, emandako a₁,a₂,...,a_k -entzako existitzen da x zenbaki oso bat kongruentzien sistemaren soluzio bakarra dena ${\displaystyle N=n_{1}*n_{2}*...*n_{k}}$ moduluarekiko.

${\displaystyle x\equiv a_{1}{\pmod {n_{1}}}}$

${\displaystyle x\equiv a_{2}{\pmod {n_{2}}}}$

${\displaystyle ...}$

${\displaystyle x\equiv a_{k}{\pmod {n_{k}}}}$

Eta sistemaren x soluzio guztiak ${\displaystyle y\equiv x{\pmod {N}}}$ 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${\displaystyle \in }$ ${\displaystyle \mathbb {\mathbb {N} } }$:

${\displaystyle {\displaystyle a^{p-1}\equiv 1{\pmod {p}}}}$

Froga:

Har ditzagun a, 2a,... (p-1)a zenbakiak eta ohartu zerrenda horretan ez daudela bi zenbaki p moduluarekiko kongruenteak direnak. Izan ere, ${\displaystyle {\displaystyle xa\equiv yb{\pmod {p}}}}$ 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, ${\displaystyle x,y\in {\{1,2,...(p-1)\}}}$ direlako.

Hartutako bi zenbakiak, p-rekin zatitzean hondar desberdinak ematen dituzte eta ez dago p-ren multiplorik haien artean. Beraz, ${\displaystyle {\displaystyle {\displaystyle a*2a*...*(p-1)a\equiv 1*2*...*(p-1){\pmod {p}}}}}$ edo ${\displaystyle {\displaystyle {\displaystyle a^{p-1}(p-1)!\equiv (p-1)!{\pmod {p}}}}}$.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 ${\displaystyle n\in \mathbb {Z} }$ eta horrekiko lehena den edozein ${\displaystyle a\in \mathbb {Z} }$${\displaystyle {\displaystyle {\displaystyle a^{\phi (n)}\equiv 1{\pmod {n}}}}}$, non ${\displaystyle \phi (n)}$ 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

${\displaystyle a_{1}\equiv b_{1}{\pmod {n}}}$

eta

${\displaystyle a_{2}\equiv b_{2}{\pmod {n}}}$

orduan

${\displaystyle a_{1}+b_{1}\equiv a_{2}+b_{2}{\pmod {n}}}$

${\displaystyle a_{1}-b_{1}\equiv a_{2}-b_{2}{\pmod {n}}}$

Adibidea:

${\displaystyle 38\equiv 14{\pmod {6}}\quad }$ eta ${\displaystyle \quad 26\equiv 8{\pmod {6}}\quad }$ izanik,

${\displaystyle {\begin{aligned}38+14\equiv 26+8{\pmod {6}}\quad \Rightarrow \quad 52\equiv 34{\pmod {6}}&\quad \Rightarrow \quad 34=5\cdot 6+4\\&\quad \Rightarrow \quad 52=8\cdot 6+4\\[1ex]38-14\equiv 26-8{\pmod {6}}\quad \Rightarrow \quad 24\equiv 18{\pmod {6}}&\quad \Rightarrow \quad 24=4\cdot 6+0\\&\quad \Rightarrow \quad 18=3\cdot 6+0.\end{aligned}}}$

Ondorioz, batuketa modularra horrela idatz daiteke:

${\displaystyle (a\!\!\!\!\mod n)\,+\,(b\!\!\!\!\mod n)\equiv a+b{\pmod {n}}}$

edo, bere baliokidea dena:

${\displaystyle ((a\!\!\!\!\mod n)\,+\,(b\!\!\!\!\mod n))\!\!\!\!\mod n=(a+b)\!\!\!\!\mod n}$

Biderketa modularra

Baldin eta

${\displaystyle a_{1}\equiv b_{1}{\pmod {n}}}$

eta

${\displaystyle a_{2}\equiv b_{2}{\pmod {n}}}$

orduan

${\displaystyle a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {n}}}$

Adibidea:

${\displaystyle 38\equiv 14{\pmod {6}}\quad }$ eta ${\displaystyle \quad 26\equiv 8{\pmod {6}}\quad }$ izanik,

${\displaystyle {\begin{aligned}38\cdot 14\equiv 26\cdot 8{\pmod {6}}\quad \Rightarrow \quad 532\equiv 208{\pmod {6}}&\quad \Rightarrow \quad 532=88\cdot 6+4\\&\quad \Rightarrow \quad 208=34\cdot 6+4\\[1ex]\end{aligned}}}$

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

${\displaystyle (a\!\!\!\!\mod n)\,(b\!\!\!\!\mod n)\equiv ab{\pmod {n}}}$

edo, bere baliokidea dena:

${\displaystyle ((a\!\!\!\!\mod n)\,(b\!\!\!\!\mod n))\!\!\!\!\mod n=(ab)\!\!\!\!\mod n}$

Berreketa modularra

${\displaystyle a,n\in \mathbb {Z} }$, ${\displaystyle \quad x\geq 0\quad }$ izanik, ${\displaystyle a^{x}}$ berreketa biderketen bidez kalkulatzean,

x berretzailea handia denean bi arazo mota sortzen dira:

• ${\displaystyle a^{x}}$ handiegia da: kalkulatu nahi izateak arazoak sor ditzake.

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

Aritmetika modularrean, ${\displaystyle a^{x}{\pmod {n}}}$ kalkulatzean:

• Zenbaki handiegien arazoa ekiditen da, ez dago ${\displaystyle a^{x}}$ kalkulatu beharrik, horrela eragiten delako.

${\displaystyle ((a{\pmod {n}})\cdot (b{\pmod {n}})){\pmod {n}}=(a\cdot b){\pmod {n}}}$

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

Alderantzizko modularra

${\displaystyle \mathbb {Z} }$ multzoko elementu guztiek ez dute alderantzizkorik, ezta ${\displaystyle \mathbb {Z} _{n}}$ multzoko guztiek alderantzizko modularrik ere.

a elementua alderantzikagarria izateko ${\displaystyle a\cdot a^{-1}=1}$ beteko duen ${\displaystyle a^{-1}}$ existitu behar da multzoan.

Alderantzizko modularraren existentzia

${\displaystyle a^{-1}{\pmod {n}}}$ existitzen da baldin eta soilik baldin ${\displaystyle zkh(a,n)=1}$ bada.

${\displaystyle \mathbb {Z} _{n}}$ multzoan alderantzikagarri diren elementuen multzoa ${\displaystyle \mathbb {Z} _{n}^{*}}$ da.

n moduluko hondarren multzo murriztua:

${\displaystyle \mathbb {Z} _{n}^{*}=\{a\in \mathbb {Z} _{n}:zkh(a,n)=1\}}$ .

Alderantzizko modularra existitzen denean, ${\displaystyle a^{-1}{\pmod {n}}}$ kalkulatzeko Euklidesen algoritmoa erabiltzen da.

Alderantzizko modularraren kalkulua Euklidesen algoritmoa erabiliz

Izan bitez ${\displaystyle a,n\in \mathbb {Z} }$ lehen erlatiboak, ${\displaystyle zkh(a,n)=1}$.

Dakigunez, ${\displaystyle \exists x,y\in \mathbb {Z} }$ non ${\displaystyle xa+yn=zkh(a,n)}$.

Hortaz,

${\displaystyle zkh(a,n)=1\quad \Leftrightarrow \quad \exists \;x,y\in \mathbb {Z} \quad }$ non ${\displaystyle \quad ax+ny=1}$.

a-ren alderantzizkoa modulu ${\displaystyle n}$ x dela ondoriozta daiteke horrela:

${\displaystyle ax+ny=1\Rightarrow ax=1+(-y)\cdot n\Rightarrow ax\equiv 1{\pmod {n}}}$ ${\displaystyle \Rightarrow a^{-1}\equiv x{\pmod {n}}}$

Euklidesen algoritmoa erabiliz x kalkulatzen da, hau da, ${\displaystyle a^{-1}}$.

Kongruentzia klaseak

${\displaystyle n}$ 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 ${\displaystyle n}$ 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 2³² 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

• Datuak: Q319400
• Multimedia: Modular arithmetic / Q319400