Es sei ´a = 8897´, ´b = 13237´, ´c = 17507´. Bestimme den ´gcd(a, b, c)´ und ´lcm(a, b, c)´ und stelle ´gcd(a, b, c)´ in der Form ´xa + yb + zc´ mit ´x, y, z´ in ´ZZ´ dar.

Approach

´13237 = 1 * 8897 + 4340´ ´8897 = 2 * 4340 + 217´ ´4340 = 20 * 217 + 0´

´gcd(13237, 8897) = 217´ ´lcm(13237, 8897) = (13237 * 8897)/gcd(13237, 8897) = 117769589/217 = 542717´

´gcd(a,b,c) = gcd(gcd(a,b),c)´

´17507 = 80 * 217 + 147´ ´217 = 1 * 147 + 70´ ´147 = 2 * 70 + 7´ ´70 = 10 * 7 + 0´

´gcd(gcd(13237, 8897), 17507) = 7´ ´lcm(lcm(13237, 8897), 17507) = 542717 * 17507/gcd(542717, 17507) = (542717 * 17507)/17507 = 542717´

A: ´147 = 17507 - 80 * 217´ ´70 = 217 - 147 = 217 - (17507 - 80 * 217) = 81 * 217 - 17507´ ´7 = 147 - 2 * 70 = 17507 - 80 * 217 - 2(81 * 217 - 17507) = 3 * 17507 - 242 * 217´

B: ´4340 = 13237 - 1 * 8897´ ´217 = 8897 - 2 * 4340 = 8897 - 2(13237 - 8897) = 3 * 8897 - 2 * 13237´

B in A:

´7 = 3 * 17507 - 242(3 * 8897 - 2 * 13237) = 3 * 17507 - 726 * 8897 + 484 * 13237´

´gcd(13237, 8897, 17507) = -726 * 8897 + 484 * 13237 + 3 * 17507´


Solution

  • ´gcd(13237, 8897, 17507) = -726 * 8897 + 484 * 13237 + 3 * 17507 = 7´ ´lcm(13237, 8897, 17507) = 542717´

  • URL:
  • Language:
  • Subjects: math
  • Type: Calculate
  • Duration: 25min
  • Credits: 3
  • Difficulty: 0.5
  • Tags: hpi gcd lcm
  • Note:
    HPI, 2014-04-14, Mathe 2, Aufgabe 7
  • Created By: adius
  • Created At:
    2014-07-25 22:27:02 UTC
  • Last Modified:
    2014-07-25 22:27:02 UTC