78.54.146.56: /* Beispiel */

2021-06-26T14:30:17Z

Beispiel

Neue Seite

Eine '''lineare Kongruenz''' bezeichnet in der [[Zahlentheorie]] eine [[diophantische Gleichung]] in Form der [[Kongruenz (Zahlentheorie)|Kongruenz]]
: <math>ax \equiv b \mod m</math>.

Sei
: <math>\operatorname{ggT}(a,m)=d</math>

Diese Kongruenz hat genau dann [[Lösung (Mathematik)|Lösungen]], wenn <math>d</math> ein [[Teilbarkeit|Teiler]] von <math>b</math> ist:
: <math>d|b</math>.

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

Die Lösungen <math>x</math> besitzen dann die Darstellung

: <math>x = r + t\cdot \frac{m}{d},\quad t \in \mathbb{Z}</math>.

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

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

Zuletzt sei wieder <math>r \in \mathbb{Z}</math> eine spezielle Lösung der linearen Kongruenz. Für jedes <math>t \in \mathbb{Z}</math> ist <math>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</math>. Hiermit sind Modulo <math>m</math> also <math>d</math> unterschiedliche Lösungen gefunden. Um sich davon zu überzeugen, dass dies alle Lösungen sind, kann man sich klarmachen, dass durch <math>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</math> eine [[Lineare diophantische Gleichung]] gegeben ist und in diesem Kontext alle Lösungen für <math>x</math> und <math>z</math> finden.

== Beispiel ==
Gesucht sind alle Lösungen der linearen Kongruenz
: <math>6x \equiv 3 \mod 27</math>.

Eine spezielle Lösung findet man durch Ausprobieren und lautet
<math>x = 14</math>.

Da <math>\operatorname{ggT}(6,27)=3</math>, gibt es drei verschiedene Lösungen modulo 27 und somit drei Äquivalenzklassen, nämlich
: <math>
\left[ {14} \right]_{27} ,\left[ {14 - 9} \right]_{27} = \left[ 5 \right]_{27} ,\left[ {14 + 9} \right]_{27} = \left[ {23} \right]_{27}
</math>

Alternativ kann man auch die Rechenregeln für Kongruenzen ausnutzen, um schneller eine Lösung zu finden:
: <math>
6x \equiv 3 \mod 27
\Leftrightarrow 2x \equiv 1 \mod 9
\Leftrightarrow_{\operatorname{ggT}(9,2) = 1} x \equiv 5 \mod 9
</math>

indem man die Gleichung zuerst mit 3 kürzt (hierbei verändert sich ebenfalls der Modul, da der <math>\operatorname{ggT}(27,3)=3\ne 1</math>) und dann mit dem Inversen von 2 multipliziert. Als Äquivalenzklasse der Lösungen erhält man dann
: <math>\left[ {5} \right]_9</math>

== Literatur ==
* {{Literatur |Autor=[[Kristina Reiss]], Gerald Schmieder |Titel=Basiswissen Zahlentheorie |Auflage=3. |Verlag=Springer Spektrum |Ort=Berlin |Datum=2014 |ISBN=978-3-642-39773-8 |Kapitel=8. Lineare und quadratische Kongruenzen}}

[[Kategorie:Zahlentheorie]]

Lineare Kongruenz - Versionsgeschichte

78.54.146.56: /* Beispiel */