Lineare Kongruenz

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

$ax\equiv b\mod m$ .

Sei

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

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

$x=r+t\cdot {\frac {m}{d}},\quad t\in \mathbb {Z}$ .

Beweis

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

$b=ar-zm=da'r-zdm'=d(a'r-zm')$ .

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

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

Zuletzt sei wieder $r\in \mathbb {Z}$ eine spezielle Lösung der linearen Kongruenz. Für jedes $t\in {\mathbb {Z}}$ ist $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$ . 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 $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$ eine Lineare diophantische Gleichung gegeben ist und in diesem Kontext alle Lösungen für und finden.

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 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 3 kürzt (hierbei verändert sich ebenfalls der Modul, da der $\operatorname {ggT}(27,3)=3\neq 1$ ) und dann mit dem Inversen von 2 multipliziert. Als Äquivalenzklasse der Lösungen erhält man dann

$\left[{5}\right]_{9}$

Literatur

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

Basierend auf einem Artikel in:

Wikipedia.de