Lineare Kongruenz

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Eine lineare Kongruenz bezeichnet in der Zahlentheorie eine diophantische Gleichung in Form der Kongruenz

.

Sei

Diese Kongruenz hat genau dann Lösungen, wenn ein Teiler von ist:

.

Sei eine spezielle Lösung, dann besteht die Lösungsmenge aus verschiedenen Kongruenzklassen.

Die Lösungen besitzen dann die Darstellung

.

Sei zunächst die lineare Kongruenz lösbar und eine Lösung. Wegen sind und . Die Bedingung ist äquivalent zu . Wähle so, dass . Äquivalente Umformung und Einsetzen liefern:

.

Hierbei ist . Also gilt bzw. .

Nun gelte . Wähle nun , sodass gilt . Das Lemma von Bézout liefert die Existenz von , sodass . Einsetzen in die vorherige Gleichung liefert: . Dies ist äquivalent zu bzw. . Wegen gilt also , was äquivalent ist zu . Damit ist durch also eine Lösung der linearen Kongruenz gegeben.

Zuletzt sei wieder eine spezielle Lösung der linearen Kongruenz. Für jedes ist . Hiermit sind Modulo also unterschiedliche Lösungen gefunden. Um sich davon zu überzeugen, dass dies alle Lösungen sind, kann man sich klarmachen, dass durch eine Lineare diophantische Gleichung gegeben ist und in diesem Kontext alle Lösungen für und finden.

Gesucht sind alle Lösungen der linearen Kongruenz

.

Eine spezielle Lösung findet man durch Ausprobieren und lautet .

Da , gibt es drei verschiedene Lösungen modulo 27 und somit drei Äquivalenzklassen, nämlich

Alternativ kann man auch die Rechenregeln für Kongruenzen ausnutzen, um schneller eine Lösung zu finden:

indem man die Gleichung zuerst mit 3 kürzt (hierbei verändert sich ebenfalls der Modul, da der ) und dann mit dem Inversen von 2 multipliziert. Als Äquivalenzklasse der Lösungen erhält man dann