Euklid. Algorithmus und modulare Arithmetik

11.11.2012, 19:42

Etwasüberfordert

Euklid. Algorithmus und modulare Arithmetik

Huhu,

Ich soll zwei Zahlen x,y ∈ Z finden, die die Gleichung 33x - 24y = 15 erfüllen.

Weiß aber leider nicht wie ich da vorgehen soll. Kann mir jemand helfen?
Weil es ja ganze Zahlen sein müssen kann man es ja nicht so einfach auflösen.. oder doch?

11.11.2012, 19:44

Etwasüberfordert1

Auf diesen Beitrag antworten »

RE: Euklid. Algorythmus und modluare Arithmetik
ach das sollte x,y element von Z heißen.
Das Zeichen wurde nicht so wirklich angezeigt.

11.11.2012, 20:28

tmo

Auf diesen Beitrag antworten »

Zunächst sollte man die Gleichung durch 3 teilen:

$\begin{eqnarray*} 11x-8y=5 \end{eqnarray*}$ .

Das Threadtitel sagt ja schon, dass man den euklidischen Algorithmus benutzen kann, um eine Lösung zu finden.

Bei solch kleinen Zahlen würde ich aber einfach systematisch ausprobieren.

Du musst ja lediglich die Zahlen $\begin{eqnarray*} x=1,3,5,7 \end{eqnarray*}$ einsetzen und bei einer davon wird sich für $\begin{eqnarray*} y \end{eqnarray*}$ eine ganze Lösung ergeben.

11.11.2012, 20:45

Etwasüberfordert2

Auf diesen Beitrag antworten »

Wieso denn x = 1, 3, 5, 7 testen? Was ist mit 2, 4, .... ?

Und ist das nicht zu sehr "getestet" und nicht gerechnet?
Kann man das nicht iwi rechnen, damit man sofort sieht zu welchem x wert ein geeigneter y-wert rauskommt?

11.11.2012, 21:15

Frage232322

Auf diesen Beitrag antworten »

Probieren ist in diesem Fall doch bisschen einfach oder? Das ist ja kein richtiger Rechenweg.
Kann mir jemand helfen, wie ich das richtig lösen kann?

11.11.2012, 22:39

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Frage232322
Probieren ist in diesem Fall doch bisschen einfach oder? Das ist ja kein richtiger Rechenweg.

Warum sollte man es sich auch einfach machen? verwirrt

"Richtig rechnen" kannst du das (wie schon erwähnt) mit dem euklidischen Algorithmus...Wie der funktioniert kannst du bestimmt in deinem Skript oder anderswo im Netz nachlesen.

11.11.2012, 22:41

Etwasüberfordert3

Auf diesen Beitrag antworten »

ok danke.

Bin jetzt schon viel weiter gekommen.

12.11.2012, 04:40

Etwasüberfordert4

Auf diesen Beitrag antworten »

Also ich habe es jetzt mit dem Euklidischen Algorithmus gemacht.
Hab jetzt den ggt von 33 und 24 bestimmt und 15 ist ein vielfaches davon.
Also weiß ich schonmal, dass es zahlen zu finden gibt.
Nur wie komm ich jetzt zu den zahlen?
Also durch den erweiterten euklidischen Algorithmus? Blicke da nicht so 100% durch.

12.11.2012, 09:31

HAL 9000

Auf diesen Beitrag antworten »

Ja klar, erst der erweiterte euklidische Algorithmus angewandt auf $\begin{eqnarray*} a,b \end{eqnarray*}$ "schleift" die nötigen Koeffizienten mit durch und liefert direkt eine Lösung $\begin{eqnarray*} (x,y) \end{eqnarray*}$ von $\begin{eqnarray*} ax+by = \operatorname{ggT}(a,b) \end{eqnarray*}$ .

P.S.: Komischerweise sind dieselben Leute, die bei ein bisschen Probieren die Nase rümpfen, gleich die ersten, die beim alternativen systematischen Verfahren hilflos dastehen. Augenzwinkern

12.11.2012, 09:54

RavenOnJ

Auf diesen Beitrag antworten »

Erstmal kann man sehen, dass 8 und 11 teilerfremd sind, woraus folgt, dass die Gleichung $\begin{align*} 11x-8y=1 \end{align*}$ mindestens ein Lösungspaar hat, z.B. $\begin{align*} (3,4) \end{align*}$ . Daraus folgt durch Multiplikation der Gleichung mit 5 ein Lösungspaar $\begin{align*} (x_0,y_0) =(15,20) \end{align*}$ für $\begin{align*} 11x - 8y = 5 \end{align*}$ .

Für alle weiteren Lösungspaare $\begin{align*} (x_k,y_k) \end{align*}$ gilt
$\begin{eqnarray*} 11(x_k -x_0) - 8(y_k-y_0) = 0\Rightarrow x_k-x_0\equiv 0 \mod 8 \land y_k-y_0\equiv 0 \mod 11 \end{eqnarray*}$ . Also ist jedes Zahlenpaar $\begin{align*} (x_0 +8k,y_0+11k), k\in\mathbb{Z} \end{align*}$ ebenfalls Lösung der Gleichung.

Gruß
Peter

12.11.2012, 11:01

Etwasüberfordert6

Auf diesen Beitrag antworten »

Also ich habe den Erweiterten Euklidschen Algorithmus angewendet, habe hier aber ein problem:
Und zwar bekomme ich sofort die Lösung raus, obwohl ich doch eigentlich nur auf den ggt kommen dürfte.
Ich zeige mal wie es bei mir aussieht. Dann kann man den Fehler denke ih am schnellsten sehen:

Mein EEA der beiden Zahlen a=75 und b=-24: (stört euch bitte nicht an den silbernen d's; hab das nur gemacht, damit man besser die Tabelle sieht - fragt nicht wie lang das gedauert hat)

adddddddddddbdddddddd[a/b]dddddddddxdddddddddddddy

33ddddddddd-24dddddddd-1ddddddddx4= -1ddddddddy4= -2 = -1-(-1*-1)
-24dddddddddd9dddddddd-2ddddddddx3= -1ddddddddy3= -1= 0-(1*1)
d9ddddddddddd6dddddddd1dddddddddx2= 1ddddddddy2= -1= 0-(1*1)
d6ddddddddddd3dddddddd2dddddddddx1= 0ddddddddy1= 1= 1-0*2)
d3ddddddddddd0ddddddddddddddddddx0= 1ddddddddy0= 0

Also der ggT von 75 und 24 ist ja 3.
Und eigentlich müsste ja 3 rauskommen, wenn ich a*(dem entsprechenden x)+b*(dem entsprechenden y) rechne.
Bsp. 9*1+6*-1=3

Aber wenn ich jetzt 33*-1 + -24*-2 rechne, dann komme ich auf 15. (Ist ja auch das Ergebnis, was mcih sehr freut), aber eigentlich sollte doch der ggt rauskommen oder?
Und wieso kommt hier keine 3 raus?
Und wenn eine 3 rauskommt, wie komme ich dann auf die x und y, damit 15 rauskommt?

Ich hoffe jemand kann mir helfen.

12.11.2012, 12:27

RavenOnJ

Auf diesen Beitrag antworten »

hast du eigentlich das gelesen, was ich geschrieben habe??

12.11.2012, 12:29

RavenOnJ

Auf diesen Beitrag antworten »

Zitat:

Original von Etwasüberfordert6
(stört euch bitte nicht an den silbernen d's; hab das nur gemacht, damit man besser die Tabelle sieht - fragt nicht wie lang das gedauert hat).

Man kann übrigens auch Tabellen in Latex schreiben.

Gruß
Peter

12.11.2012, 12:32

Etwasüberfordert7

Auf diesen Beitrag antworten »

Ja habe ich gelesen. Ok danke für den Tipp mit der Tabelle.

Wir sollen aber die Aufgabe mit dem EEA berechnen.

12.11.2012, 13:07

Etwasüberfordert8

Auf diesen Beitrag antworten »

kann mir denn jemand eine Rückmeldung zum EEA geben?
Wieso ich nicht auf die 3 komme, sondern auf die 15?
Hab ich irgendwo was falsch gerechnet?

12.11.2012, 13:31

HAL 9000

Auf diesen Beitrag antworten »

Es gibt im Detail verschiedene Darstellungen des EEA, und der Teufel liegt hier bei der Fehlersuche nun mal im Detail: Schreib also bitte mal, nach welcher algorithmischen Vorschrift du hier konkret vorgegangen bist, vielleicht als Link.

Außerdem verwirrt mich folgendes: Bestimmst du hier nun ggT(75,24) oder ggT(33,24) ? Irgendwie schwankst du zwischen beiden Varianten hin und her, was es nicht gerade einfacher macht, deine Ausführungen nachzuvollziehen. unglücklich

Zumindest hierauf kann ich eine Antwort geben:

Zitat:

Original von Etwasüberfordert6
Und wenn eine 3 rauskommt, wie komme ich dann auf die x und y, damit 15 rauskommt?

Hast du $\begin{eqnarray*} x,y \end{eqnarray*}$ mit $\begin{eqnarray*} 33x-24y=3 \end{eqnarray*}$ gefunden, dann musst du das ganze ja lediglich noch mit $\begin{eqnarray*} \frac{15}{3}=5 \end{eqnarray*}$ multiplizieren, d.h.

$\begin{eqnarray*} 33\cdot (5x) - 24\cdot (5y) = 15 \end{eqnarray*}$ ,

eine Gleichungslösung ist dann also $\begin{eqnarray*} (5x,5y) \end{eqnarray*}$ .

12.11.2012, 13:42

Etwasüberforder9

Auf diesen Beitrag antworten »

meinte natürlich den ggT(33,-24)

Naja hatte zuerst den normalen euklidischen Algorithmus angewendet un ddann von unten wieder rauf gerechnet, wie man es ja beim EEA macht.
Nur bin ich mir wegen der -24 nicht so sicher, wie ich das berechnen soll. Ich glaube, dass genau da das Problem liegt. Habe es jetzt schon oft nachgerechnet und komme immer wieder auf das gleiche raus.
Aber ich meine wenn ich als ggT 3 habe, dann müsste ja ja auch 3 rauskommen, wenn ich 33*x+24*y rechne.

Oder muss ich einfach den ggT von 33 und 24 berechnen und dann beim y-Wert das vorzeichen tauschen?

12.11.2012, 14:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Etwasüberforder9
und dann von unten wieder rauf gerechnet, wie man es ja beim EEA macht.

"Man" macht es eben nicht immer gleich: Es gibt auch Varianten des EEA, bei dem man simultan schon mal die Koeffizienten berechnet, man also nicht erst "wieder rauf" rechnen muss. Was den Vorteil hat, dass man immer nur die letzte Zeile im Speicher halten muss.

Zitat:

Original von Etwasüberforder9
Oder muss ich einfach den ggT von 33 und 24 berechnen und dann beim y-Wert das vorzeichen tauschen?

Ist auf alle Fälle eine gute Idee, verringert auch beim manuellen Rechnen die Fehlergefahr wg. falscher Vorzeichen u.ä. Augenzwinkern

Neue Frage »

Antworten »

Euklid. Algorithmus und modulare Arithmetik

Verwandte Themen