Lineare Kongruenz

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

<math>ax \equiv b \mod m</math>.

Sei

<math>\operatorname{ggT}(a,m)=d</math>

Diese Kongruenz hat genau dann Lösungen, wenn <math>d</math> ein Teiler von <math>b</math> ist:

<math>d|b</math>.

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

Die Lösungen <math>x</math> besitzen dann die Darstellung

<math>x = r + t\cdot \frac{m}{d},\quad t \in \mathbb{Z}</math>.

Beweis

Sei zunächst die lineare Kongruenz <math>ax \equiv b \mod m</math> lösbar und <math>r \in \mathbb{Z}</math> eine Lösung. Wegen <math>\operatorname{ggT}(a,m) = d</math> sind <math>a' := \frac{a}{d} \in \mathbb{Z}</math> und <math>m' := \frac{m}{d} \in \mathbb{Z}</math>. Die Bedingung <math>ar \equiv b \mod m</math> ist äquivalent zu <math>m|(ar - b)</math>. Wähle <math>z \in \mathbb{Z}</math> so, dass <math>zm = ar - b</math>. Äquivalente Umformung und Einsetzen liefern:

<math>b = ar - zm = da'r - zdm' = d(a'r - zm')</math>.

Hierbei ist <math>a'r - zm' \in \mathbb{Z}</math>. Also gilt <math>d | b</math> bzw. <math>\operatorname{ggT}(a,m) | b</math>.

Nun gelte <math>\operatorname{ggT}(a,m) = d|b</math>. Wähle nun <math>z \in \mathbb{Z}</math>, sodass gilt <math>b = zd</math>. Das Lemma von Bézout liefert die Existenz von <math>s, t \in \mathbb{Z}</math>, sodass <math>d = sa + tm</math>. Einsetzen in die vorherige Gleichung liefert: <math>b = z(sa+tm) = zsa + ztm</math>. Dies ist äquivalent zu <math>ztm = b - zsa</math> bzw. <math>-ztm = zsa - b</math>. Wegen <math>-zt \in \mathbb{Z}</math> gilt also <math>m|(zsa-b)</math>, was äquivalent ist zu <math>zsa \equiv b \mod m</math>. Damit ist durch <math>r := zs</math> also eine Lösung der linearen Kongruenz <math>ax \equiv b \mod m</math> gegeben.

Zuletzt sei wieder <math>r \in \mathbb{Z}</math> eine spezielle Lösung der linearen Kongruenz. Für jedes <math>t \in \mathbb{Z}</math> ist <math>b \equiv ar \equiv ar + \frac{a}{d} \cdot tm = ar + at \cdot \frac{m}{d} = a(r+t \cdot \frac{m}{d}) \mod m</math>. Hiermit sind Modulo <math>m</math> also <math>d</math> unterschiedliche Lösungen gefunden. Um sich davon zu überzeugen, dass dies alle Lösungen sind, kann man sich klarmachen, dass durch <math>ax \equiv b \mod m \Leftrightarrow m|ax-b \Leftrightarrow \exists z \in \mathbb{Z}: zm = ax-b \Leftrightarrow \exists z\in \mathbb{Z}: ax + (-z)m = b</math> eine Lineare diophantische Gleichung gegeben ist und in diesem Kontext alle Lösungen für <math>x</math> und <math>z</math> finden.

Beispiel

Gesucht sind alle Lösungen der linearen Kongruenz

<math>6x \equiv 3 \mod 27</math>.

Eine spezielle Lösung findet man durch Ausprobieren und lautet <math>x = 14</math>.

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

<math>

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

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

<math>

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

</math>

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

<math>\left[ {5} \right]_9</math>

Literatur

Kristina Reiss, Gerald Schmieder: Basiswissen Zahlentheorie. 3. Auflage. Springer Spektrum, Berlin 2014, ISBN 978-3-642-39773-8, 8. Lineare und quadratische Kongruenzen.