Kongruentzia (zenbakien teoria)

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

$a\equiv b{\pmod {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{\pmod {m}}$

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

$a\;{\bmod {\;}}m=b\;{\bmod {\;}}m$

• $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

$\exists k\in \mathbb {Z} \quad 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{\pmod {m}}$, $a$ guztietarako.
• Simetria erlazioa: $a\equiv b{\pmod {m}}$ bada, $b\equiv a{\pmod {m}}$ da.
• Iragate-erlazioa (trantsitiboa): $a\equiv b{\pmod {m}}$ eta $b\equiv c{\pmod {m}}$ badira, $a\equiv c{\pmod {m}}$ izango da.

$a\equiv b{\pmod {m}}$ eta $k\in \mathbb {Z}$ badira:

• $a(+-)k\equiv b(+-)k{\pmod {m}}$
• $ak\equiv bk{\pmod {m}}$
• $a^{k}\equiv b^{k}{\pmod {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{\pmod {m}}$-rekiko lehena bada, $b$ ere $m$-rekiko lehena izango da.
• $k$ $m$-rekiko lehena bada, orduan $\exists {\displaystyle h^{-1}}$ non ${\displaystyle kh^{-1}\equiv 1{\pmod {m}}}$. Horregatik, zatiketari buruz aritzeak zentzua du eta beraz, zuzena da ${\displaystyle {\frac {a}{k}}\equiv {\frac {b}{k}}{\pmod {m}}}$ non definizioz, ${\displaystyle a/k=ak^{-1}\,}$.
• Aurrekoaren ondorio bezala, modulu bereko bi kongruentzia badaude, ${\displaystyle a\equiv b{\pmod {m}}}$ eta ${\displaystyle c\equiv d{\pmod {m}}}$, batu, kendu edo biderka ditzakegu, kongruentziak egiaztatzeko: ${\displaystyle a+c\equiv b+d{\pmod {m}}}$ eta ${\displaystyle ac\equiv bd{\pmod {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{\pmod {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, ${\bar {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\ {\mbox{(mod 4)}}\$, 7 = 3 + 1 ⋅ 4 baita.
• $82\equiv 1\ {\mbox{(mod 9)}}\$, 82 = 1 + 9 ⋅ 9 baita.
• $27\equiv 0\ {\mbox{(mod 3)}}\$, 27 = 0 + 3 ⋅ 3 baita.
• $-3\equiv 3\ {\mbox{(mod 6)}}\$, -3 = 3 + -1 ⋅ 6 baita.
• $2\not \equiv 5\ {\mbox{(mod 6)}}\$, 2 ≠ 5 + k ⋅ 6 baita.

Kongruentzia linealak

$a\equiv b{\pmod {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{\pmod {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
• (Ingelesez) Kongruentziak mathworld-en
• (Gaztelaniaz) Kongruentziak. Aljebra eskolak.

• Datuak: Q3773677