(a) ´a = 551´, ´b = 703´

Euklidischer Algorithmus:

´703 = 1 * 551 + 152´ ´551 = 3 * 152 + 95´ ´152 = 1 * 95 + 57´ ´95 = 1 * 57 + 38´ ´57 = 1 * 38 + 19´ ´38 = 2 * 19 + 0´

Also ´ggT(551, 703) = 19´.

kgV:

´kgV(a,b) = (a * b)/(ggT(a,b)) = (551 * 703)/19 = 387353/19 = 20387´

Erweiterter Euklidischer Algorithmus (Rückwärtseinsetzen):

´19 = 57 - 1 * 38´ ´19 = 57 - 1 * (95 - 57) = 2 * 57 - 95´ ´19 = 2 * (152 - 95) - 95 = 2 * 152 - 3 * 95´ ´19 = 2 * 152 - 3 * (551 - 3 * 152) = 11 * 152 - 3 * 551´ ´19 = 11 * (703 - 551) - 3 * 551 = 11 * 703 - 14 * 551´

Mit ´a = 551´, ´b = 703´:

´ggT(551, 703) = 551 * (-14) + 703 * 11´

also ´x = -14´, ´y = 11´.

---

(b) ´a = 1291´, ´b = 1039´

Euklidischer Algorithmus:

´1291 = 1 * 1039 + 252´ ´1039 = 4 * 252 + 31´ ´252 = 8 * 31 + 4´ ´31 = 7 * 4 + 3´ ´4 = 1 * 3 + 1´ ´3 = 3 * 1 + 0´

Also ´ggT(1291, 1039) = 1´ (teilerfremd).

kgV:

´kgV(a,b) = (a * b)/(ggT(a,b)) = 1291 * 1039 = 1341349´

Erweiterter Euklidischer Algorithmus (Rückwärtseinsetzen):

´1 = 4 - 1 * 3´ ´1 = 4 - 1 * (31 - 7 * 4) = 8 * 4 - 1 * 31´ ´1 = 8 * (252 - 8 * 31) - 1 * 31 = 8 * 252 - 65 * 31´ ´1 = 8 * 252 - 65 * (1039 - 4 * 252) = 268 * 252 - 65 * 1039´ ´1 = 268 * (1291 - 1039) - 65 * 1039 = 268 * 1291 - 333 * 1039´

Mit ´a = 1291´, ´b = 1039´:

´ggT(1291, 1039) = 1291 * 268 + 1039 * (-333)´

also ´x = 268´, ´y = -333´.

---

(c) ´a = 13961´, ´b = 6509´

Euklidischer Algorithmus:

´13961 = 2 * 6509 + 943´ ´6509 = 6 * 943 + 851´ ´943 = 1 * 851 + 92´ ´851 = 9 * 92 + 23´ ´92 = 4 * 23 + 0´

Also ´ggT(13961, 6509) = 23´.

kgV:

´kgV(a,b) = (a * b)/(ggT(a,b)) = (13961 * 6509)/23 = 90871249/23 = 3950923´

Erweiterter Euklidischer Algorithmus (Rückwärtseinsetzen):

´23 = 851 - 9 * 92´ ´23 = 851 - 9 * (943 - 851) = 10 * 851 - 9 * 943´ ´23 = 10 * (6509 - 6 * 943) - 9 * 943 = 10 * 6509 - 69 * 943´ ´23 = 10 * 6509 - 69 * (13961 - 2 * 6509) = 148 * 6509 - 69 * 13961´

Mit ´a = 13961´, ´b = 6509´:

´ggT(13961, 6509) = 13961 * (-69) + 6509 * 148´

also ´x = -69´, ´y = 148´. ```