jäännöslukemat

Jäännöslukemat ovat jäännöksiä, joita syntyy, kun kokonaislukuja jaetaan kiinteällä positiivisella luvulla n. Jokaiselle luvulle a voidaan löytää jäännösluku r, siten että a = qn + r ja 0 ≤ r < n. Tällöin a ≡ r (mod n).

Kaksi lukua a ja b ovat kongruentteja modulo n, jos niillä on sama jäännösluku r, eli a ≡ b (mod n). Moduulin n jäännöslukemien joukko {0,1,...,n−1} muodostaa täydellisen jäännöslukemien järjestelmän modulo n.

Operatiivisesti modulo n voidaan laskea siten, että luvut vähennetään tai lisätään niin, että ne saavat jäännösluvun 0 ≤ r < n. Tulokset säilyttävät kongruenssin: jos a ≡ r (mod n) ja b ≡ s (mod n), niin a + b ≡ r + s (mod n) ja a · b ≡ r · s (mod n).

Esimerkki: 17 jaetaan 5:lla, jäännösluku on 2, koska 17 = 3·5 + 2; 17 ≡ 2 (mod 5). Myös 7 ≡ 2 (mod 5) ja 7 + 13 ≡ 2 + 3 ≡ 0 (mod 5).

Jäännöslukemien käsite on keskeinen modulaarisessa laskennassa, luvun teorian ja kryptografian kontekstissa sekä erilaisissa algoritmeissa.