Lineare Kongruenz

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine lineare Kongruenz bezeichnet in der Zahlentheorie eine Kongruenz der Form

.

Sei

Diese Kongruenz hat genau dann Lösungen, wenn gilt:

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

Die x besitzen dann die Darstellung

Beispiel[Bearbeiten | Quelltext bearbeiten]

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 somit schneller eine Lösung zu finden:

indem man die Gleichung zuerst mit dem Inversen von 3 multipliziert (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