kongruenzgleichung

26.03.2011, 22:13

xxmaxx

kongruenzgleichung

hi,

kann mir bitte jemand die Vorgehensweise von kongruenzgleichungen erklären z.b. bei
5x kongruent 2 mod 11

also der ggt von(5,11) = 1

Mit hilfe von Euklid bestimme ich das inverse und komme auf 1 = 5* (-2) + 11* (1)

und wie geht es jetzt weiter? die lösung sagt: man findet 9 · 5 kongruent 1 mod 11 also
x kongruent 9 · 2 = 18 kongruent 7 mod 11

keine ahnung wie man auf das ergebnis kommt.

thx

26.03.2011, 22:26

Bjoern1982

Auf diesen Beitrag antworten »

Erstmal die Frage an dich: Ist dir klar warum du eigentlich das (multiplikativ) Inverse von 5 modulo 11 hier brauchst ?

26.03.2011, 22:31

xxmaxx

Auf diesen Beitrag antworten »

ehrlich gesagt nein.

27.03.2011, 00:18

Bjoern1982

Auf diesen Beitrag antworten »

Du brauchst das wegen dem Zusammenhang $\begin{eqnarray*} a \cdot a^{-1}=1 \end{eqnarray*}$ , denn damit folgt für deine gegebene lineare Kongruenz:

$\begin{eqnarray*} 5^{-1} \cdot 5 \cdot x \equiv 5^{-1} \cdot 2\ mod\ 11 \end{eqnarray*}$

Man ist also zunächst auf der Suche nach einer Zahl, welche mit 5 multipliziert kongruent zu 1 modulo 11 ist, denn wenn man eine solche gefunden hat, dann hat man das x sozusagen isoliert.
Da wir hier mit Restklassen bzw Restklassenringen arbeiten, gilt natürlich $\begin{eqnarray*} 5^{-1} \equiv -2\ mod\ 11=-2+11 \cdot k \end{eqnarray*}$ mit k aus Z.
Ist damit klar wie die 9 entsteht bzw warum man sie ebenso wählen darf ?

27.03.2011, 10:50

xxmaxx

Auf diesen Beitrag antworten »

Hmm so ganz versteh ichs nicht:

Zitat:

Du brauchst das wegen dem Zusammenhang $\begin{eqnarray*} a \cdot a^{-1}=1 \end{eqnarray*}$ , denn damit folgt für deine gegebene lineare Kongruenz:

ok soweit klar, dann:

Zitat:

$\begin{eqnarray*} 5^{-1} \cdot 5 \cdot x \equiv 5^{-1} \cdot 2\ mod\ 11 \end{eqnarray*}$ Man ist also zunächst auf der Suche nach einer Zahl, welche mit 5 multipliziert kongruent zu 1 modulo 11 ist, denn wenn man eine solche gefunden hat, dann hat man das x sozusagen isoliert.

schön und gut. wo kommt jz aber das $\begin{eqnarray*} 5^{-1} \end{eqnarray*}$ her? Mein inverses is ja
-2

Zitat:

Ist damit klar wie die 9 entsteht bzw warum man sie ebenso wählen darf ?

ich denk weil 9 und -2 den gleichen rest liefert

und wie ich dann auf das ergebnis von komme versteh ich auch nicht so ganz:

$\begin{eqnarray*} x \equiv 9*2 = 18 \equiv 7 \mod 11 \end{eqnarray*}$

ich dachte man muss auf beiden seiten mit dem inversen multiplizieren?

fragen über fragen

27.03.2011, 11:25

xxmaxx

Auf diesen Beitrag antworten »

mir ist grad ein licht aufgegangen. und ich hab mich schon gewundert woher das 5^-1 kommt smile

vielen dank

27.03.2011, 12:20

Bjoern1982

Auf diesen Beitrag antworten »

Damit nun alles klar oder gibts noch Fragen ?

Neue Frage »

Antworten »

kongruenzgleichung

Verwandte Themen