kongruenzen

16.01.2007, 10:37	Yogi Löw	Auf diesen Beitrag antworten »
kongruenzen Hallo, könnte mir mal jemand erklären wie man mit Kongruenzen rechnet, am besten anhand des folgenden Beispiels (wie kommt die Umformung zustande?): $\begin{eqnarray} 5x\equiv 4 mod 7 \\6x\equiv 8 mod 20 \\7x\equiv 3 mod 9 \\\\------>\\\\x\equiv 5 mod 7 \\x\equiv 8 mod 10 \\x\equiv 3mod 9\\\ \end{eqnarray}$ besten dank...
16.01.2007, 12:21	therisen	Auf diesen Beitrag antworten »
Mal die erste Umformung: Das Inverse zu $\begin{eqnarray} 5 \end{eqnarray}$ in $\begin{eqnarray} \mathbb Z / 7\mathbb Z \end{eqnarray}$ ist gegeben durch $\begin{eqnarray} 5^{-1} \equiv 3 \pmod 7 \end{eqnarray}$ , also ist $\begin{eqnarray} x \equiv 4\cdot 5^{-1} \equiv 4\cdot 3 = 12 \equiv 5 \pmod 7 \end{eqnarray}$ . Gruß, therisen
16.01.2007, 14:53	Yogi Löw	Auf diesen Beitrag antworten »
...also irgendwie steh ich n bischen aufm Schlauch.Ich bring im Moment alles durcheinander. Wie finde ich denn genau das Inverse? Vielleicht nochmal am Bsp der zweiten Umformung demonstrieren? oder an dem folgenden Bsp: ich soll bestimmen, ob die Kongruenz lösbar ist : $\begin{eqnarray} 18x^2+3x+2\equiv 0 mod 31 \end{eqnarray}$ in der Musterlösung, die ich nicht verstehe, ist folgende Umformung gemacht worden : $\begin{eqnarray} 18x^2+3x+2\equiv 0 mod 31 \Rightarrow x^2+26x+7\equiv 0 mod 31 \Rightarrow (x+13)^2\equiv 162\equiv 7 mod 31 \end{eqnarray}$ Dann ergibt sich mit dem Legendre Symbol, dass 7 quadratischer Rest mod 31 ist und somit ist die Konruenz lösbar. Wäre nett, wenn mir jemand diese Umformung schrittweise erklären könnte...
16.01.2007, 15:04	therisen	Auf diesen Beitrag antworten »
Das Inverse kann man z.B. mit dem erweiterten euklidischen Algorithmus bestimmen (oder durch Raten ). Die Gleichung $\begin{eqnarray} 18x^2 + 3x + 2 \equiv 0 \pmod {31} \end{eqnarray}$ wurde einfach mit $\begin{eqnarray} 18^{-1} \equiv 19 \pmod {31} \end{eqnarray}$ durchmultipliziert. Es ist dann $\begin{eqnarray} 3\cdot 19 \equiv 26 \end{eqnarray}$ und $\begin{eqnarray} 2\cdot 19 \equiv 7 \end{eqnarray}$ Gruß, therisen
16.01.2007, 15:10	Yogi Löw	Auf diesen Beitrag antworten »
wie komme ich auf die 19 ????
16.01.2007, 15:17	piloan	Auf diesen Beitrag antworten »
hi die kannst du mit dem erweiterten euklidischen algorithmus bestimmen: http://de.wikipedia.org/wiki/Erweiterter...her_Algorithmus
Anzeige

16.01.2007, 15:52	Divergenz	Auf diesen Beitrag antworten »
Hallo, alles was man hierfür wissen muss, findet man wie so häufig bei wikipedia: http://de.wikipedia.org/wiki/Kongruenz_%28Zahlentheorie%29
16.01.2007, 15:56	Yogi Löw	Auf diesen Beitrag antworten »
entschuldigt bitte, dass ich mich so blöd anstelle, aber mit dem erweiterten euklidischen algorithmus bestimme ich doch eine linearkombination bzgl des ggT, oder nicht? wie komme ich dann damit auf das inverse? hab schon drei seiten vollgekritzelt, komm aber nicht drauf. bitte am Bsp $\begin{eqnarray} 5^{-1}\equiv 3 mod7 \end{eqnarray}$ ...
16.01.2007, 16:15	therisen	Auf diesen Beitrag antworten »
Der erweiterte euklidische Algorithmus angewandt auf $\begin{eqnarray} (5,7) \end{eqnarray}$ liefert $\begin{eqnarray} -2\cdot 7+3\cdot 5 = 1 \end{eqnarray}$ und das modulo 7 betrachtet liefert eben $\begin{eqnarray} 3\cdot 5 \equiv 1 \pmod 7 \end{eqnarray}$ Ist keine große Kunst

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »