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.

  1. ´a = 629´, ´b = 323´
  2. ´a = 4768´, ´b = 3327´
  3. ´a = 913´, ´b = 1079´
Approach

Teil 1

´629 = 1 * 323 + 306´ ´323 = 1 * 306 + 17´ ´306 = 18 * 17 + 0´

´gcd(629, 323) = 17´ ´lcm(629, 323) = (629 * 323)/gcd(629, 323) = 203167/17 = 11951´

´306 = 629 - 1 * 323´ ´17 = 323 - 1 * 306 = 323 - (629 - 323) = 323 - 629 + 323 = 2 * 323 - 629´

´gcd(629, 323) = 2 * 323 - 629´

Teil 2

´4768 = 1 * 3327 + 1441´ ´3327 = 2 * 1441 + 445´ ´1441 = 3 * 445 + 106´ ´445 = 4 * 106 + 21´ ´106 = 5 * 21 + 1´ ´21 = 21 * 1 + 0´

´gcd(4768, 3327) = 1´ ´lcm(4768, 3327) = (4768 * 3327)/gcd(4768, 3327) = 15863136/1 = 15863136´

´1441 = 4768 - 1 * 3327´ ´445 = 3327 - 2 * 1441 = 3327 - 2(4768 - 3327) = 3 * 3327 - 2 * 4768´ ´106 = 1441 - 3 * 445 = 1441 - 3(3 * 3327 - 2 * 4768) =´´4768 - 3327 - 9 * 3327 + 6 * 4768 =´´7 * 4768 - 10 * 3327´ ´21 = 445 - 4 * 106 = 3 * 3327 - 2 * 4768 - 4(7 * 4768 - 10 * 3327) = 43 * 3327 - 30 * 4768´ ´1 = 106 - 5 * 21 = 7 * 4768 - 10 * 3327 - 5(43 * 3327 - 30 * 4768) =´´157 * 4768 - 225 * 3327´

´gcd(4768, 3327) = 157 * 4768 - 225 * 3327´

Teil 3

´1079 = 1 * 913 + 166´ ´913 = 5 * 166 + 83´ ´166 = 2 * 83 + 0´

´gcd(1079, 913) = 83´ ´lcm(1079, 913) = (1079 * 913)/gcd(1079, 913) = 985127/83 = 11869´

´166 = 1079 - 1 * 913´ ´83 = 913 - 5 * 166 = 913 - 5(1079 - 913) = 6 * 913 - 5 * 1079´

´gcd(1079, 913) = 6 * 913 - 5 * 1079´


Solution
  • 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´

  • URL:
  • Language:
  • Subjects: math
  • Type: Calculate
  • Duration: 35min
  • Credits: 3
  • Difficulty: 0.3
  • Tags: hpi gcd lcm
  • Note:
    HPI, 2014-04-14, Mathe 2, Aufgabe 6
  • Created By: adius
  • Created At:
    2014-07-25 22:23:40 UTC
  • Last Modified:
    2014-07-25 22:24:20 UTC