Lineare Kongruenz

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

a x \equiv b mod m

.

Sei

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}, t \in ℤ

.

Beweis

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

b = a r - z m = d a^{'} r - z d m^{'} = d (a^{'} r - z m^{'})

.

Hierbei ist $a^{'} r - z m^{'} \in ℤ$ . Also gilt $d | b$ bzw. $ggT (a, m) | b$ .

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

Zuletzt sei wieder $r \in ℤ$ eine spezielle Lösung der linearen Kongruenz. Für jedes $t \in ℤ$ ist $b \equiv a r \equiv a r + \frac{a}{d} \cdot t m = a r + a t \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 $a x \equiv b mod m \Leftrightarrow m | a x - b \Leftrightarrow \exists z \in ℤ : z m = a x - b \Leftrightarrow \exists z \in ℤ : a x + (- 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

6 x \equiv 3 mod 27

.

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

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

{[14]}_{27}, {[14 - 9]}_{27} = {[5]}_{27}, {[14 + 9]}_{27} = {[23]}_{27}

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

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

{[5]}_{9}

Literatur

Vorlage:Literatur

Lineare Kongruenz

Beweis

Beispiel

Literatur

Navigationsmenü

Suche