Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Algorithmus berechnet: ggT(a, b) und Koeffizienten x, y ∈ Z so dass ggT(a, b) = xa + yb

Anwendung: a ist Modul, b ∈ Za invertierbar gdw. ggT(a, b) = 1;

Bsp:

39	17	5	2	1	0
/	2	3	2	2
1	0	1	-3	7	-17
0	1	-2	7	-16	39

39/17 = 2 R 2 -> 2 unten 5 rechts
17/5 = 3 R 2 -> 3 unten 2 rechts

Zeile 3/4:
1 - 0 * 2 = 1    / 0 - 1 * 3 = -3
0 - 1 * 2 = -2  / 1 - (-2) * 3 = 7   ....