kongruenssi

Kongruenssi modulo n on matemaattinen käsite, jota käytetään ilmaisemaan, että kaksi kokonaislukua eroavat toisistaan monikertaisella luvulla n. Kaksi lukua a ja b ovat kongruentteja modulo n, jos a ≡ b (mod n) ja erotus a − b on jaollinen luvulla n. Moduli n on positiivinen kokonaisluku. Kongruenssirelaatio modulo n on ekvivalenssirelaatio: se on refleksiivinen (a ≡ a (mod n) kaikilla a), symmetrinen ja transitiivinen. Jokaiselle n muodostuu n jäännösluokkaa, joita kutsutaan kongruenssiluokiksi; ne vastaavat residuoja 0, 1, ..., n−1. Esimerkki: 23 ≡ 5 (mod 6) ja 17 ≡ 5 (mod 6).

Peruslaskut: jos a ≡ b (mod n) ja c ≡ d (mod n), niin a + c ≡ b + d (mod n), a − c ≡ b − d (mod n) sekä ac ≡ bd (mod n). Suurien lukujen käsittelyssä voidaan käyttää residuumin vähentämistä: esimerkiksi 12345 ≡ 345 (mod 1000). Jos gcd(a,n) = 1, luvulla a on käänteinen modulo n, eli löytyy luku a^{-1} niin, että a·a^{-1} ≡ 1 (mod n). Kongruensseja sovelletaan moniin kohteisiin: lukuteoriaan, kryptografiaan sekä laskennallisiin ratkaisuihin; merkittäviä esimerkkejä ovat Kiinan jäännöslauseke sekä modulaarinen laskenta RSA-tyyppisissä kryptosysteemeissä. Kongruenssin käsite mahdollistaa suurien lukujen hallinnan pienissä, moduloituissa arvoissa.