Modulo rechnen

24.03.2010, 20:08	Pätti	Auf diesen Beitrag antworten »
Modulo rechnen Meine Frage: Hallöchen alsooo ich hab ein problem. Bestimme eine Zahl a ? {0, 1, . . . , 4710} mit: $\begin{eqnarray} 7= a1001 mod 4711 \end{eqnarray}$ Kann mir jemand sagen wie ich a sinnvoll bestimme? Meine Ideen:* Ich hab versucht den Euklidischen Algorithmus anzuwenden und somit das Multiplikativ Inverse von 1001 mod 4711 zu bestimmen. Kam als Ergebnis -80 raus. kann aber nicht sein laut Aufgabenstellung. Hab viele Sachen hin und her probiert kam aber nicht aufs Ergebnis. Habs dann Mittels "Bruthe Force" und Excel gelöst. Das Ergebnis ist 593. Aber da ich darauf auch in der Prüfung ohne Taschenrechner kommen soll bin ich absolut hilflos .. kann mir einer eklären wie ich schneller auf die Lösung komme. Eyklisdischer Algorithmus bei diesen Zahlen ist übrigens auch nicht besonders schnell. Vielen Dank schon mal
24.03.2010, 22:47	chrizke	Auf diesen Beitrag antworten »
-80 ist richtig, du musst es nur noch in den passenden Intervall 'umrechnen'.
24.03.2010, 23:26	Pätti	Auf diesen Beitrag antworten »
ok habsch gemacht komm ich auf a = 4151 ... kann aber nicht die lösung sein weil 1001*4151 = 49 (mod 4711) und nicht = 7...jetzt bin ich verwirrt also wie gesagt mit excel und bruthe force komme ich auf 593 und dann stimmt die gleichung auch .. kannst du mir das noch anders erklären?
24.03.2010, 23:35	chrizke	Auf diesen Beitrag antworten »
Es ist ja auch $\begin{eqnarray} -80\not\equiv 4151 \pmod{4711} \end{eqnarray}$ Es gilt vielmehr: $\begin{eqnarray} -80\equiv -80+4711 \pmod{4711} \end{eqnarray}$
25.03.2010, 01:00	mYthos	Auf diesen Beitrag antworten »
brute force, alles andere ist brutal und nicht bruthal mY+
25.03.2010, 13:50	Pätti	Auf diesen Beitrag antworten »
Ahhh ok klar verrechnet ^^ weiß wie du das meinst Danke Gibt es noch eine andere Möglichkeit das zu berechnen? Bei diesen Zahlen wird das ganz schnell ziemlich stressig das zu berechen. Warum gibt es eig. mehrere Lösungen?
Anzeige

25.03.2010, 14:25	AD	Auf diesen Beitrag antworten »
Zur Lösung solcher linearer Kongruenzen $\begin{eqnarray} ax \equiv b \bmod m \qquad () \end{eqnarray}$ mit "großen" Modulen $\begin{eqnarray} m \end{eqnarray}$ zieht du am besten den Erweiterten Euklidischer Algorithmus (EEA) zur Bestimmung von $\begin{eqnarray} g=\operatorname{ggT}(a,m) \end{eqnarray}$ hinzu: Der bestimmt nämlich zum einen $\begin{eqnarray} g \end{eqnarray}$ selbst, was zur Klärung der Lösbarkeit von () benötigt wird, denn () besitzt genau dann Lösungen, wenn $\begin{eqnarray} g \mid b \end{eqnarray}$ . Ist das der Fall, dann ermöglichen die vom EEA gelieferten Koeffizienten $\begin{eqnarray} r,s \end{eqnarray}$ mit der Eigenschaft $\begin{eqnarray} ra + sm = g \end{eqnarray}$ auch gleich den Schlüssel zur Lösung. Dann folgt aus () nämlich $\begin{eqnarray} rb \equiv rax = (g-sm)x \equiv gx \bmod m \end{eqnarray}$ , was zu den $\begin{eqnarray} g \end{eqnarray}$ Lösungen $\begin{eqnarray} x_k = r\cdot \frac{b}{g} + k \cdot \frac{m}{g} \end{eqnarray}$ mit $\begin{eqnarray} k=0,1,\ldots,g-1 \end{eqnarray}$ führt. Hier eine Javascript-Seite zur Online-Berechnung mittels EEA: http://www.mirsky.de/ggt.php, die liefert für $\begin{eqnarray} a=1001,m=4711 \end{eqnarray}$ die Werte $\begin{eqnarray} r=-80,s=17,g=7 \end{eqnarray}$ mit den Lösungen $\begin{eqnarray} x_k = -80 + k\cdot 673 \end{eqnarray}$ für $\begin{eqnarray} k=0,1,\ldots,6 \end{eqnarray}$ .
25.03.2010, 15:28	Pätti	Auf diesen Beitrag antworten »
huiii ... danke !!! hab zwar ne weile gebraucht bis ich kapiert hab was da stand ^^ .. aber das macht die sache um einiges einfacher

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »