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

$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 $m$ also $d$ 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 $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 $x=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}$