Das Verfahren, ganzzahlige Lösungen x für Kongruenzen der Form a x ≡ b (mod n) zu finden, wobei a, b und n gegebene ganze Zahlen und n>0 ist.

Prinzip

Die Kongruenz a x ≡ b (mod n) ist genau dann lösbar, wenn d = gcd(a,n) den Wert b teilt; ist das erfüllt, teilt man durch d, erhält eine äquivalente Kongruenz mit Modul n/d und nutzt modulare Inversen für den reduzierten Koeffizienten.

Demonstration

Beispiel: Löse 14 x ≡ 6 (mod 20). gcd(14,20)=2 teilt 6, durch 2 teilen: 7 x ≡ 3 (mod 10). Das Inverse von 7 modulo 10 ist 3, also x ≡ 3·3 ≡ 9 (mod 10). Zurück zum Modul 20 ergeben sich die Klassen x ≡ 9 und x ≡ 19 (mod 20).

Fehlanwendung

Das Versuch, a modulo n zu invertieren, wenn gcd(a,n) ≠ 1, oder das Ignorieren des Faktors d führt zu falschen Aussagen über Eindeutigkeit oder zum Verlust von Lösungen.

Konsequenz

Richtige Anwendung liefert alle Restklassen ganzer Lösungen und eine reduzierte Kongruenz, deren Lösungsmenge durch den Modulus n/d parametriert ist; sie wandelt einen Existenztest in eine konstruktive Lösung um, nützlich in der algorithmischen Zahlentheorie.

Umkehrung

Statt x für eine einzelne lineare Kongruenz zu bestimmen, kann man das Problem umkehren (a oder n aus beobachteten Restklassen rekonstruieren) oder nichtlineare Kongruenzen betrachten, die andere Löskriterien benötigen.

Abgrenzung

Gilt nur für lineare Kongruenzen mit ganzzahligen Koeffizienten und n>0; schließt nichtlineare Kongruenzen, Kongruenzen über nicht-ganzen Ringen und Lösungen in Q aus, sofern sie nicht auf äquivalente ganze Kongruenzen zurückgeführt werden.

Semantische Spannung

Wird oft mit dem Lösen linearer Gleichungen über dem Ring Z/nZ als abstraktem Objekt vermischt; die Spannung liegt zwischen konstruktiven, algorithmischen Lösungsbeschreibungen und rein strukturellen Aussagen über Moduln über Z/nZ.

Synthese

Das Lösen linearer Kongruenzen ist ein konstruktiver Prozess: Prüfung der Teilbarkeit durch gcd(a,n), Reduktion des Moduls und anschließende Bestimmung von modularen Inversen oder einer Parametrisierung aller Restklassen, die a x ≡ b (mod n) erfüllen.