Lineare Kongruenz

Kongruenz einer speziellen Form

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

.

BeweisBearbeiten

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.

BeispielBearbeiten

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

 

LiteraturBearbeiten