Kapitel 2Aufbau24 Min.
Erste lineare Kongruenzen und die Kürzungsfalle
Kongruenznotation und sichere Rechenregeln · Abschnitt 7 von 64
Definition
Lineare Kongruenz
Eine Gleichung sucht ganze Zahlen , deren Restklasse die Kongruenz erfüllt. Eine Lösung steht immer für alle kongruenten Vertreter.
Gelöstes Beispiel
Beispiel modulo 7
Für ist 3 eine Inverse von 5, denn . Multiplikation mit 3 liefert .
Achtung
Nicht wie bei gewöhnlichen Gleichungen kürzen
, aber . Der Faktor 2 darf hier nicht gekürzt werden, weil er mit 6 einen gemeinsamen Teiler besitzt.
Hinweis für Begleitende
Ausblick auf Teil II
Wann eine lineare Kongruenz lösbar ist, wie viele Lösungsklassen sie besitzt und wie Inverse mit dem erweiterten euklidischen Algorithmus berechnet werden, folgt im nächsten Teil.