0 Daumen
1,4k Aufrufe

ich habe ein Problem mit folgender Aufgabe:

Verwenden Sie den euklidischen Algorithmus, um für jedes der folgenden Beispiele den ggT(a,b) zu berechnen. Außerdem bestimmen Sie jeweils ganze Zahlen x,y ∈ℤ, so dass xa+yb=ggT(a,b). Zeigen Sie alle Schritte und Rechnungen.

Mit den Zahlenbeispielen kam ich klar, das letzte Beispiel jedoch lautet: a=30n+2 und b=12n+1 für alle n ∈ℕ.

Für die Lösung sollen wir folgende Tabelle verwenden, die ich soweit ausgefüllt habe, wie ich konnte:

j          rj-1          qj          rj           rj+1          xj          yj

0         -              -       30n+2   12n+1       1          0

1       30n+2    2      12n+1      6n             0          1

2        12n+1    2         6n          1                           -2

3        6n           6n        1           0                           5    

Den ggT habe ich also gefunden (1), aber ich bekomme den Wert für xj nicht raus.

Ich habe bis jetzt gerechnet: (für Zeile j=2)

y2=0-1*2=-2

dann:

6n=x2*(30n+2)+(-2)*(12n+1)

umgeformt zu 6n=30n*x2+2x2-24n-2

dann komme ich nicht mehr weiter.

Genauso bei Zeile j=3:

y3=1+2*2=5

dann:

1=x3*(30n+2)+5*(12n+1)

umgeformt zu 1=30n*x3+2x3+60n+5.

Für eure Hilfe wäre ich euch sehr dankbar!

Avatar von

2 Antworten

0 Daumen
-2 * (30n+2) + 5* (12n+1) = 1
kann man ja so sehen, oder aus dem oberen ableiten allerdings
"rückwärts"

1*(12n+1)  -2*6n     =  1
also   -2*6n   =   1  -  1* (12n+1)

und
1 * (30n+2) -2 * (12n+1) =  1*6n
also mit -2 malnehmen
-2 * (30n+2) +4 * (12n+1) =  -2*6n
einsetzen

-2 * (30n+2) +4 * (12n+1) = 1  -  1* (12n+1)        | +1* (12n+1)
-2 * (30n+2) + 5* (12n+1) = 1
Avatar von 287 k 🚀
0 Daumen

Für x2 benutzt du ja diese Formel: xj+1=xj-qj*xj also x2=1-(2*0) was ja 1 ergbit.

Für x3 dann das selbe Spiel also x3=0-(2*1) was -2 ergibt.

Dann kannste am Ende in die Formel einsetzen: 1 = -2*(30n+2)+5*(12n+1)

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community