euklidischer Algorithmus mit Termen/Variablen

Question

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          r_j-1          q_j          r_j           r_j+1          x_j          y_j

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 x_j nicht raus.

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

y₂=0-1*2=-2

dann:

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

umgeformt zu 6n=30n*x₂+2x₂-24n-2

dann komme ich nicht mehr weiter.

Genauso bei Zeile j=3:

y₃=1+2*2=5

dann:

1=x₃*(30n+2)+5*(12n+1)

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

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

Answer 1

-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

Answer 2

Für x₂ benutzt du ja diese Formel: x_j+1=x_j-q_j*x_j also x₂=1-(2*0) was ja 1 ergbit.

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

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