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\ {\mbox{(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\ {\mbox{(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 \mathbb {R} ,y\not =0$, on $x{\mbox{(mod y)}}=x-y\lfloor x/y\rfloor +ny$ jollakin $n\in \mathbb {Z}$ ja $x{\mbox{(mod 0)}}=x$

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

Esimerkkejä

• $7\equiv 3\ {\mbox{(mod 4)}}\$, koska 7 = 1 $\cdot$ 4 + 3, ts. 7−3 on jaollinen 4:llä.
• $82\equiv 1\ {\mbox{(mod 9)}}\$, koska 82−1 (81 = 9 $\cdot$ 9) on jaollinen 9:llä.
• $27\equiv 0\ {\mbox{(mod 3)}}\$, koska 27 on jaollinen 3:lla.
• $-3\equiv 3\ {\mbox{(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

• Kaleva, Osmo: Numeerinen analyysi. (Opintomoniste 163) Tampere: TTKK, 1993. ISBN 951-721-941-5
• Häsä, Jokke; Rämö, Johanna: Johdatus abstraktiin algebraan. Helsinki: Gaudeamus, 2015. ISBN 978-952-495-361-0