Bestimme mit Hilfe des Euklidischen Algorithmus für die folgenden Zahlenpaare ´(a, b)´ jeweils ´gcd(a, b)´, ´lcm(a, b)´ und stelle den größten gemeinsamen Teiler in der Form ´gcd(a, b) = ax + by (x, y in ZZ)´ dar.
- ´a = 629´, ´b = 323´
- ´a = 4768´, ´b = 3327´
- ´a = 913´, ´b = 1079´
"Teil 1\n\n´629 = 1 \* 323 + 306´\n´323 = 1 \* 306 + 17´\n´306 = 18 \* 17 + 0´\n\n´gcd(629, 323) = 17´\n´lcm(629, 323) = (629 \* 323)/gcd(629, 323) = 203167/17 = 11951´\n\n´306 = 629 - 1 \* 323´\n´17 = 323 - 1 \* 306 = 323 - (629 - 323) = 323 - 629 + 323 = 2 \* 323 - 629´\n\n´gcd(629, 323) = 2 \* 323 - 629´\n\n\nTeil 2\n\n´4768 = 1 \* 3327 + 1441´\n´3327 = 2 \* 1441 + 445´\n´1441 = 3 \* 445 + 106´\n´445 = 4 \* 106 + 21´\n´106 = 5 \* 21 + 1´\n´21 = 21 \* 1 + 0´\n\n´gcd(4768, 3327) = 1´\n´lcm(4768, 3327) = (4768 \* 3327)/gcd(4768, 3327) = 15863136/1 = 15863136´\n\n´1441 = 4768 - 1 \* 3327´\n´445 = 3327 - 2 \* 1441 = 3327 - 2(4768 - 3327) = 3 \* 3327 - 2 \* 4768´\n´106 = 1441 - 3 \* 445 = 1441 - 3(3 \* 3327 - 2 \* 4768) =´´4768 - 3327 - 9 \* 3327 + 6 \* 4768 =´´7 \* 4768 - 10 \* 3327´\n´21 = 445 - 4 \* 106 = 3 \* 3327 - 2 \* 4768 - 4(7 \* 4768 - 10 \* 3327) = 43 \* 3327 - 30 \* 4768´\n´1 = 106 - 5 \* 21 = 7 \* 4768 - 10 \* 3327 - 5(43 \* 3327 - 30 \* 4768) =´´157 \* 4768 - 225 \* 3327´\n\n´gcd(4768, 3327) = 157 \* 4768 - 225 \* 3327´\n\n\nTeil 3\n\n´1079 = 1 \* 913 + 166´\n´913 = 5 \* 166 + 83´\n´166 = 2 \* 83 + 0´\n\n´gcd(1079, 913) = 83´\n´lcm(1079, 913) = (1079 \* 913)/gcd(1079, 913) = 985127/83 = 11869´\n\n´166 = 1079 - 1 \* 913´\n´83 = 913 - 5 \* 166 = 913 - 5(1079 - 913) = 6 \* 913 - 5 \* 1079´\n\n´gcd(1079, 913) = 6 \* 913 - 5 \* 1079´"
Teil 1
´gcd(629, 323) = 2 * 323 - 629 = 17´ ´lcm(629, 323) = 11951´
Teil 2
´gcd(4768, 3327) = 157 * 4768 - 225 * 3327 = 1´ ´lcm(4768, 3327) = 15863136´
Teil 3
´gcd(1079, 913) = 6 * 913 - 5 * 1079 = 83´ ´lcm(1079, 913) = 11869´
HPI, 2014-04-14, Mathe 2, Aufgabe 6
2014-07-25 22:24:20 UTC
2014-07-25 22:24:20 UTC