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 d ein Teiler von b ist:

d|b.

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

Die Lösungen x besitzen dann die Darstellung

{\displaystyle 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 {\displaystyle \operatorname {ggT} (a,m)=d} sind {\displaystyle a':={\frac {a}{d}}\in \mathbb {Z} } und {\displaystyle m':={\frac {m}{d}}\in \mathbb {Z} }. Die Bedingung {\displaystyle ar\equiv b\mod m} ist äquivalent zu {\displaystyle m|(ar-b)}. Wähle {\displaystyle z\in \mathbb {Z} } so, dass {\displaystyle zm=ar-b}. Äquivalente Umformung und Einsetzen liefern:

{\displaystyle b=ar-zm=da'r-zdm'=d(a'r-zm')}.

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

Nun gelte {\displaystyle \operatorname {ggT} (a,m)=d|b}. Wähle nun {\displaystyle z\in \mathbb {Z} }, sodass gilt {\displaystyle b=zd}. Das Lemma von Bézout liefert die Existenz von {\displaystyle s,t\in \mathbb {Z} }, sodass {\displaystyle d=sa+tm}. Einsetzen in die vorherige Gleichung liefert: {\displaystyle b=z(sa+tm)=zsa+ztm}. Dies ist äquivalent zu {\displaystyle ztm=b-zsa} bzw. {\displaystyle -ztm=zsa-b}. Wegen {\displaystyle -zt\in \mathbb {Z} } gilt also {\displaystyle m|(zsa-b)}, was äquivalent ist zu {\displaystyle zsa\equiv b\mod m}. Damit ist durch {\displaystyle 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 {\displaystyle 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 m also d unterschiedliche Lösungen gefunden. Um sich davon zu überzeugen, dass dies alle Lösungen sind, kann man sich klarmachen, dass durch {\displaystyle 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 x und z 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

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 05.07. 2021