Es sei ´a = 5957´, ´b = 6601´, ´c = 10619´.

Bestimme ´ggT(a, b, c)´ und ´kgV(a, b, c)´ und stelle ´ggT(a, b, c)´ in der Form ´xa + yb + zc´ mit ´x, y, z in Z´ dar.


Approach

Faktorisierung der Zahlen:

  • ´5957 = 7 · 23 · 37´
  • ´6601 = 7 · 23 · 41´
  • ´10619 = 7 · 37 · 41´

ggT

Der ggT ist das Produkt der gemeinsamen Primfaktoren mit jeweils kleinstem Exponenten. Nur die ´7´ kommt in allen drei Zahlen vor:

´ggT(a, b, c) = 7´

kgV

Das kgV ist das Produkt aller auftretenden Primfaktoren mit jeweils größtem Exponenten, also ´7 · 23 · 37 · 41´:

´kgV(a, b, c) = 7 · 23 · 37 · 41 = 244237´

Darstellung als Linearkombination

Wir nutzen ´ggT(a, b, c) = ggT(ggT(a, b), c)´.

Schritt 1: ´ggT(a, b)´ mit dem erweiterten euklidischen Algorithmus.

´6601 = 1 · 5957 + 644´ ´5957 = 9 · 644 + 161´ ´644 = 4 · 161 + 0´

Also ´ggT(5957, 6601) = 161 = 7 · 23´. Rückwärtseinsetzen:

´161 = 5957 - 9 · 644´ ´= 5957 - 9 · (6601 - 5957) = 10 · 5957 - 9 · 6601´

Damit:

´161 = 10a - 9b´

Schritt 2: ´ggT(161, c)´.

´10619 = 65 · 161 + 154´ ´161 = 1 · 154 + 7´ ´154 = 22 · 7 + 0´

Also ´ggT(161, 10619) = 7´. Rückwärtseinsetzen:

´7 = 161 - 1 · 154´ ´= 161 - (10619 - 65 · 161) = 66 · 161 - 10619´

Schritt 3: Einsetzen.

Ersetze ´161 = 10a - 9b´:

´7 = 66 · (10a - 9b) - 10619´ ´= 660a - 594b - c´


Solution

  • ´ggT(a, b, c) = 7 = 660 · a - 594 · b - 1 · c´

    mit ´(x, y, z) = (660, -594, -1)´.

    Probe: ´660 · 5957 - 594 · 6601 - 10619 = 3931620 - 3920994 - 10619 = 7´ ✓

    Die Lösung ist nicht eindeutig: Zu jedem Tripel ´(x, y, z)´ kann man Vielfache der Relationen ´(b/d_(ab), -a/d_(ab), 0)´ etc. addieren, da ´7 | a, b, c´ jeweils Spielraum lässt.

  • URL:
  • Language: Deutsch
  • Subjects: math
  • Type: Calculate
  • Duration: 25min
  • Credits: 6
  • Difficulty: 0.5
  • Tags: HPI Mathematik 2
  • Note:
  • Created By: ad-si
  • Created At:
    2013-04-28 10:07:53 UTC
  • Last Modified:
    2026-06-01 13:34:43 UTC