Registrieren Passwort vergessen?

Lineare Kongruenz

23. Nov 2008, 18:32

Eine lineare Kongruenz bezeichnet in der Zahlentheorie eine Kongruenz der Form

ax \equiv b \mod m.

Sei

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

Diese Kongruenz hat genau dann Lösungen, wenn gilt:

d | b

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

Die x besitzen dann die Darstellung

x = r + t*m/d, t \in \mathbb{Z}

[Bearbeiten] 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 somit 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 dem Inversen von 3 multipliziert (hierbei verändert sich ebenfalls der Modul, da der \operatorname{ggT}(27,3)=3\ne 1 und dann mit dem Inversen von 2 multipliziert. Als Äquivalenzklasse der Lösungen erhält man dann

\left[ {5} \right]_9
Von „http://de.wikipedia.org/wiki/Lineare_Kongruenz“
Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.
In Kooperation mit Lycos Europe Network