Kongruentzia (zenbakien teoria)

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

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

Honela irakurtzen da: ${\displaystyle a}$ kongruente ${\displaystyle b}$ modulu ${\displaystyle m}$.

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

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

• ${\displaystyle a}$ kongruente ${\displaystyle b}$ modulu ${\displaystyle m}$

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

• ${\displaystyle a}$ zati ${\displaystyle m}$-ren hondarra ${\displaystyle b}$ zati ${\displaystyle m}$-ren hondarra da

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

• ${\displaystyle m}$-k zehatz zatitzen du ${\displaystyle a}$ eta ${\displaystyle b}$-ren kendura

${\displaystyle m\mid a-b}$

• ${\displaystyle a}$ idatz daiteke ${\displaystyle b}$-ren eta ${\displaystyle m}$-ren multiplo baten batura bezala

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

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

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

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

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

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

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

Edozein kongruentzia-erlazio bezala, n kongruentzia-modulua baliokidetasun-erlazio bat da, eta a zenbaki osoaren baliokidetasun-klasea, ${\displaystyle {\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 [${\displaystyle a}$] bezala ere adieraz daiteke.

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

${\displaystyle 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:

${\displaystyle 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.

• Aritmetika modularra
• Kongruentzien ebazpena
• Baliokidetasun klasea

• Dibisibilitatearen teoria eta kongruentziak UEU Iruñea 1979
• (Ingelesez) Kongruentziak mathworld-en
• (Gaztelaniaz) Kongruentziak. Aljebra eskolak.