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ää ${\displaystyle a\equiv r\ {\mbox{(mod b)}}\ }$, joka luetaan: a on kongruentti r:n kanssa modulo b.^[1]

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

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

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

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

Esimerkkejä

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

Lähteet

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.