Lineare Kongruenz

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*m/d, t \in \mathbb{Z}$

Beispiel

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$