Lineare Kongruenz

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

${\displaystyle ax\equiv b\mod m}$.

Sei

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

Diese Kongruenz hat genau dann Lösungen, wenn ${\displaystyle d}$ ein Teiler von ${\displaystyle b}$ ist:

${\displaystyle d|b}$.

Sei ${\displaystyle r}$ eine spezielle Lösung, dann besteht die Lösungsmenge aus ${\displaystyle d}$ verschiedenen Kongruenzklassen.

Die Lösungen ${\displaystyle 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 ${\displaystyle ax\equiv b\mod m}$ lösbar und ${\displaystyle 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 ${\displaystyle ax\equiv b\mod m}$ gegeben.

Zuletzt sei wieder ${\displaystyle r\in \mathbb {Z} }$ eine spezielle Lösung der linearen Kongruenz. Für jedes ${\displaystyle 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 ${\displaystyle m}$ also ${\displaystyle 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 ${\displaystyle x}$ und ${\displaystyle z}$ finden.

Beispiel

Gesucht sind alle Lösungen der linearen Kongruenz

${\displaystyle 6x\equiv 3\mod 27}$.

Eine spezielle Lösung findet man durch Ausprobieren und lautet ${\displaystyle x=14}$.

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

${\displaystyle \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:

${\displaystyle 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 ${\displaystyle \operatorname {ggT} (27,3)=3\neq 1}$) und dann mit dem Inversen von 2 multipliziert. Als Äquivalenzklasse der Lösungen erhält man dann

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

Literatur

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