Lineare Kongruenzen

1. Definition:

Sind a,b und m > 0 ganze Zahlen, dann wird

lineare Kongruenz (in der Unbekannten x) genannt.

2. Lösungen:

Eine ganze Zahl x^*, die die Bedingung erfüllt, ist eine Lösung dieser Kongruenz. Jede ganze Zahl, die zu x^* kongruent modulo m ist, ist ebenfalls eine Lösung. Will man alle Lösungen von (5.273) angeben, dann genügt es also, die paarweise modulo m inkongruenten ganzen Zahlen zu finden, die die Kongruenz erfüllen. Die Kongruenz (5.273) ist genau dann lösbar, wenn ein Teiler von b ist. Die Anzahl der Lösungen modulo m ist dann gleich .
Ist insbesondere , dann ist die Kongruenz modulo m eindeutig lösbar.

Lösungsverfahren:

Es gibt verschiedene Lösungsverfahren für lineare Kongruenzen. Z.B. kann man die Kongruenz in die diophantische Gleichung ax+my=b umformen und zunächst eine spezielle Lösung (x⁰,y⁰) der linearen diophantischen Gleichung a'x+m'y=b' mit ermitteln.
Die Kongruenz ist wegen modulo m' eindeutig lösbar, und es gilt:

Die Kongruenz hat modulo m genau Lösungen:

Beispiel

mod 315 ist lösbar, denn ist Teiler von 6; es gibt 3 Lösungen modulo 315.
mod 105 ist eindeutig lösbar: mod 105 (s. Lösungsverfahren für n=2). Also sind 94, 199 und 304 die Lösungen von mod 315.