Kongruenssi (lukuteoria)

Kongruenssirelaatio merkitsee sitä, että kahdesta luvusta jää sama jakojäännös, kun ne jaetaan samalla kolmannella luvulla. Kongruenssille käytetään yleisesti merkintää $a\equiv r\text{(mod b)}$, joka luetaan: a on kongruentti r:n kanssa modulo b.

Kahden kokonaisluvun kongruenssi voidaan määritellä jakoyhtälön

$a,b\in \mathbb{Z}$

$a\equiv r\text{(mod b)}$, jos a = kb + r jollakin kokonaisluvulla k, toisin sanoen b|(a-r), toisin sanoen erotus a-r on jaollinen b:llä.

Kongruenssi voidaan myös yleistää kahdelle mielivaltaiselle reaaliluvulle seuraavasti: jos $x,y\in ℝ,y=0$, on $x\text{(mod y)}=x-y\lfloor x/y\rfloor +ny$ jollakin $n\in \mathbb{Z}$ ja $x\text{(mod 0)}=x$

Kongruensseja voidaan käyttää jaksollisten funktioiden merkitsemiseen. Esimerkiksi koska $\tan x=\tan (x+\pi )$, voidaan kirjoittaa $\tan x\equiv \tan x\text{(mod }\pi )$.

Esimerkkejä

• $7\equiv 3\text{(mod 4)}$, koska 7 = 1 $\cdot$ 4 + 3, ts. 7−3 on jaollinen 4:llä.
• $82\equiv 1\text{(mod 9)}$, koska 82−1 (81 = 9 $\cdot$ 9) on jaollinen 9:llä.
• $27\equiv 0\text{(mod 3)}$, koska 27 on jaollinen 3:lla.
• $-3\equiv 3\text{(mod 6)}$, koska −3−3 (=−6) on jaollinen 6:lla.

Kongruenssirelaatio on ekvivalenssirelaatio, joten se jakaa kokonaislukujen joukon ekvivalenssiluokkiin.

Katso myös

• Modulaarinen aritmetiikka

Kirjallisuutta

• Malline:Kirjaviite
• Malline:Kirjaviite