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.