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]

Tämä artikkeli esittelee kongruenssin käsitettä lukuteoriassa, kielitieteellisestä käsitteestä katso kongruenssi (kielitiede).

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 )}$.

Ominaisuuksia

Kongruenssilla on seuraavia ominaisuuksia:^[2]

• Jos ${\displaystyle a\equiv b\ {\mbox{(mod 0)}}}$, niin ${\displaystyle a=b}$
• Joko ${\displaystyle a\equiv b\ {\mbox{(mod m)}}}$ tai ${\displaystyle a\not \equiv b\ {\mbox{(mod m)}}}$
• ${\displaystyle a\equiv a\ {\mbox{(mod m)}}}$
• Jos ${\displaystyle a\equiv b\ {\mbox{(mod m)}}}$, niin ${\displaystyle b\equiv a\ {\mbox{(mod m)}}}$
• Jos ${\displaystyle a\equiv b\ {\mbox{(mod m)}}}$ ja ${\displaystyle b\equiv c\ {\mbox{(mod m)}}}$, niin ${\displaystyle a\equiv c\ {\mbox{(mod m)}}}$.

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