Kongruenzsysteme

Kongruenzsysteme bestehen aus einer Menge von Gleichungen der Form x ≡ a_i (mod n_i), wobei x eine ganze Zahl ist. Sie beschreiben alle Werte von x, die zu allen Bedingungen gleichzeitig passen.

Existenz und Eindeutigkeit: Ein solches System besitzt genau dann eine Lösung, wenn für alle Indizes i, j gilt: a_i ≡ a_j (mod gcd(n_i, n_j)). Falls diese Konsistenz gegeben ist, existiert mindestens eine Lösung. Sind zusätzlich die Moduli paarweise teilerfremd (gcd(n_i, n_j) = 1 für alle i ≠ j), dann ist die Lösung eindeutig modulo N = lcm(n_1, ..., n_k).

Lösungsmethoden: Im Fall paarweise teilerfremder Moduli liefert der Chinesische Restsatz eine eindeutige Lösung modulo N. Allgemein lässt sich das System schrittweise lösen, indem man zwei Kongruenzen nach der anderen kombiniert. Für x ≡ a (mod n) und x ≡ b (mod m) mit d = gcd(n, m) gilt: Falls a ≡ b (mod d), existiert eine Lösung modulo l = lcm(n, m). Man suche t, so dass n/d · t ≡ (b − a)/d (mod m/d) erfüllt ist; t existiert, weil gcd(n/d, m/d) = 1. Dann setzt man x = a + n t und erhält eine neue Kongruenz x ≡ x_0 (mod l). Den Vorgang kann man weiterführen, bis alle Bedingungen berücksichtigt sind.

Anwendungen und Kontext: Kongruenzsysteme finden sich in der Zahlentheorie, der Kryptographie (beispielsweise bei der Optimierung mithilfe des CRT in RSA) und in Algorithmen zur Bestimmung gemeinsamer Restklassen. Generalisierungen umfassen Systeme Ax ≡ b (mod n) sowie weitere modulare Gleichungssysteme.

Beispiel: x ≡ 2 mod 3 und x ≡ 3 mod 5. Mit gcd(3,5)=1 existiert eine Lösung eindeutig modulo 15; eine Lösung ist x ≡ 8 (mod 15).