Kongruentsid

Kongruentsid on matemaatiline mõiste, mis kirjeldab seost kahe täisarvu vahel, kui nende vahe on jagatav täisarvuga n. Täisarvu a ja b kohta öeldakse, et a ≡ b (mod n), kui n jagab a − b.

Kongruentsus moodustab täisarvude kohta võrdlusklasside süsteemi modulo n. Kaks arvu kuuluvad samasse jäägklass mod n, kui nad on võrdsed modulo n. Seetõttu jaguneb täisarvude hulk n erinevasse jäägklassisse: 0, 1, ..., n−1. Nimetatakse ka jäägklasside kogumit Z/nZ.

Arvutused kongruentsidega järgivad tavapäraseid operatsioonireegleid: kui a ≡ b (mod n) ja c ≡ d (mod n), siis a + c ≡ b + d (mod n) ja ac ≡ bd (mod n). Iga arv a on kongruentne oma jäägiga r, kus 0 ≤ r < n, ehk a ≡ r (mod n). Lisamine ja korrutamine on jäägklassidel hästi defineeritud, mistõttu Z/nZ on ring (ja kui n on algarv, siis Z/nZ on ka keha).

Lahendused lineaarsetes kongruentsides: ax ≡ b (mod n) on lahendatav täpselt siis, kui gcd(a, n) jagab b. Kui d = gcd(a, n), on modulo n olemas täpselt d erist lahendust. Lahenduste leidmiseks kasutatakse laienetud Euklid'i algoritmi.

Hiina jäägiteoreem: kui n1, ..., nk on paarikaupa jagamatud (gcd(n_i, n_j) = 1 iga i ≠ j), siis süsteem x ≡ a_i (mod n_i) omab unikaalset lahendust modulo N = ∏ n_i.

Kasutused: kongruentside teooria on keskne arvutiteaduses ja number theory ning leidab rakendusi krüptograafias (nt RSA), kodeerimises ja mitmesugustes arvutusalgoritmides.