Kongruentzia (zenbakien teoria)

Zenbakien teorian, kongruentzia terminoa bi zenbaki oso $a$ eta $b$, $m\ne 0$ zenbaki arruntaz —modulua deiturikoa— zatitzerakoan, hondar berdina dutela adierazteko erabiltzen da. Honako notazio hau erabiliz:

$a\equiv b(\mathrm{mod}m)$

Honela irakurtzen da: $a$ kongruente $b$ modulu $m$.

$a$ eta $b$ $m$ moduluarekiko kongruenteak dira, baldin eta soilik baldin $m$ moduluak $a$ eta $b$-ren arteko desberdintza zehazki zatitzen badu, hau da, $m|a-b$. Beste modu batera esanda, $a$ eta $b$-k $m$-rekiko zatiketan, hondar bera uzten badute. Gainera, baiezta daiteke $a$ zenbakia $b$-ren batura eta $m$-ren multiplo bezala idatzi daitekela, $m|a-b$ denez, $mk=a-b$ izango da $k\in \mathbb{Z}$ batentzat eta orduan, $a=b+mk$.

Adierazpen baliokideak

Kongruentziak hainbat modu matematikotan adieraz daitezke. Esate baterako, adierazpen hauek baliokideak dira:

• $a$ kongruente $b$ modulu $m$

$a\equiv b(\mathrm{mod}m)$

• $a$ zati $m$-ren hondarra $b$ zati $m$-ren hondarra da

$amodm=bmodm$

• $m$-k zehatz zatitzen du $a$ eta $b$-ren kendura

$m\mid a-b$

• $a$ idatz daiteke $b$-ren eta $m$-ren multiplo baten batura bezala

$\mathrm{\exists }k\in \mathbb{Z}a=b+km$

Propietateak

Kongruentziak $m$ moduluarekiko $a$ eta $b$ zenbakien arteko baliokidetasun-erlazio bat adierazten du, hurrengo erlazioak betetzen dituelako:

• Erlazio bihurkaria (erreflexiboa): $a\equiv a(\mathrm{mod}m)$, $a$ guztietarako.
• Simetria erlazioa: $a\equiv b(\mathrm{mod}m)$ bada, $b\equiv a(\mathrm{mod}m)$ da.
• Iragate-erlazioa (trantsitiboa): $a\equiv b(\mathrm{mod}m)$ eta $b\equiv c(\mathrm{mod}m)$ badira, $a\equiv c(\mathrm{mod}m)$ izango da.

$a\equiv b(\mathrm{mod}m)$ eta $k\in \mathbb{Z}$ badira:

• $a(+-)k\equiv b(+-)k(\mathrm{mod}m)$
• $ak\equiv bk(\mathrm{mod}m)$
• $a^k\equiv b^k(\mathrm{mod}m)$ $k>0$

Gainera, $a$ eta $b$ elkarrekiko lehenak badira, beste zenbait propietate ere betetzen dituzte, besteak beste:

• $a$ zenbakia $m$ eta $a\equiv b(\mathrm{mod}m)$-rekiko lehena bada, $b$ ere $m$-rekiko lehena izango da.
• $k$ $m$-rekiko lehena bada, orduan $\mathrm{\exists }{h}^{-1}$ non $k{h}^{-1}\equiv 1(\mathrm{mod}m)$. Horregatik, zatiketari buruz aritzeak zentzua du eta beraz, zuzena da $\frac{a}{k}\equiv \frac{b}{k}(\mathrm{mod}m)$ non definizioz, $a/k=a{k}^{-1}$.
• Aurrekoaren ondorio bezala, modulu bereko bi kongruentzia badaude, $a\equiv b(\mathrm{mod}m)$ eta $c\equiv d(\mathrm{mod}m)$, batu, kendu edo biderka ditzakegu, kongruentziak egiaztatzeko: $a+c\equiv b+d(\mathrm{mod}m)$ eta $ac\equiv bd(\mathrm{mod}m)$.
• Fermaten teorema txikia: Izan bitez $p$ lenbaki lehena eta $a\in \mathbb{N}$. $a$, $p$-ren multiploa ez bada orduan: $a^{(p-1)(q-1)}\equiv 1(\mathrm{mod}pq)$
• Izan bitez $p$ eta $q$ zenbaki lehenak eta $a\in \mathbb{N}$. $a$ ez bada ez $p$-ren ez $q$-ren multiploa, orduan:

Kongruentzia klaseak

Edozein kongruentzia-erlazio bezala, n kongruentzia-modulua baliokidetasun-erlazio bat da, eta a zenbaki osoaren baliokidetasun-klasea, $\overline{a_n}$ bidez adierazten dena, {… , a − 2n, a − n, a, a + n, a + 2n, …} multzoa da. Multzo hori, a modulo n-rekin kongruenteak diren zenbaki osoek osatzen dute. Baliokidetasun-erlazioa denez, baliokidetasun-klaseak defini daitezke. Klase bakoitzean m-rekin zatitzean hondar bera ematen duten zenbaki osoak daude. Beraz, m hondar desberdin daudenez, m baliokidetasun-klase daude. Bakoitzaren ordezkari modura 0, 1, . . . eta m − 1 zenbakiak har daitezke. Baliokidetasun klasea [$a$] bezala ere adieraz daiteke.

Adibideak

• $7\equiv 3\text{(mod 4)}$, 7 = 3 + 1 ⋅ 4 baita.
• $82\equiv 1\text{(mod 9)}$, 82 = 1 + 9 ⋅ 9 baita.
• $27\equiv 0\text{(mod 3)}$, 27 = 0 + 3 ⋅ 3 baita.
• $-3\equiv 3\text{(mod 6)}$, -3 = 3 + -1 ⋅ 6 baita.
• $2\equiv ̸5\text{(mod 6)}$, 2 ≠ 5 + k ⋅ 6 baita.

Kongruentzia linealak

$a\equiv b(\mathrm{mod}m)$ motako ekuazioen ebazpen orokorrean, d = zkh(a, n) zatitzaile komunetako handienak b zatitzen badu, orduan x soluzioa aurki daiteke kongruentziarako: Euklidesen algoritmoak r eta s osoak sortzen ditu, non d = ra + sn. Hortaz, x = rb/d soluzio bat da. Gainerako soluzioak x modulo n/d -rekin kongruenteak diren zenbakiak dira.

Adibidez, ondoko kongruentziak 4 soluzio ditu:

$12x\equiv 20(\mathrm{mod}28)$

zkh (12, 28) = 4-k 20 zatitzen duelako. Euklidesen algoritmoak ondokoa ematen du: (-2)*12 + 1*28 = 4, hau da, r = -2 eta s = 1. Beraz, soluzio bat x = -2*20/4 = -10 izango da, eta -10 = 4 mod(7). Beste soluzio guztiak ere 4 modulo 7-rekin kongruenteak izan beharko dira.

Ikus, gainera

• Aritmetika modularra
• Kongruentzien ebazpena
• Baliokidetasun klasea

Kanpo estekak

• Dibisibilitatearen teoria eta kongruentziak UEU Iruñea 1979
• Txantiloi:En Kongruentziak mathworld-en
• Txantiloi:Es Kongruentziak. Aljebra eskolak.