Lineare Kongruenz

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

Eine lineare Kongruenz bezeichnet in der Zahlentheorie eine Kongruenz der Form

ax \equiv b \mod m.

Sei

\operatorname{ggT}(a,m)=d

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

d|b

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

Die x besitzen dann die Darstellung

x = r + t\cdot m/d, t \in \mathbb{Z}

Beispiel[Bearbeiten]

Gesucht sind alle Lösungen der linearen Kongruenz

6x \equiv 3 \mod 27.

eine spezielle Lösung findet man durch Ausprobieren und lautet r = 14.

Da \operatorname{ggT}(6,27)=3, gibt es drei verschiedene Lösungen modulo 27 und somit drei Äquivalenzklassen, nämlich


\left[ {14} \right]_{27} ,\left[ {14 - 9} \right]_{27}  = \left[ 5 \right]_{27} ,\left[ {14 + 9} \right]_{27}  = \left[ {23} \right]_{27}

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


 6x \equiv 3 \mod 27
  \Leftrightarrow 2x \equiv 1 \mod 9
  \Leftrightarrow_{\operatorname{ggT}(9,2) = 1} x \equiv 5 \mod 9

indem man die Gleichung zuerst mit dem Inversen von 3 multipliziert (hierbei verändert sich ebenfalls der Modul), da der \operatorname{ggT}(27,3)=3\ne 1 und dann mit dem Inversen von 2 multipliziert. Als Äquivalenzklasse der Lösungen erhält man dann

\left[ {5} \right]_9