TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS12/Beispiel 44

From VoWi
Jump to navigation Jump to search

Angabe[edit]

Man bestimme zwei ganze Zahlen x, y, welche die Gleichung 451x + 176y = 11 erfüllen.

Lösungsansatz[edit]

Kürzen der Gleichung

  451x + 176y = 11 | : 11
    41x + 16y = 1

Bestimmen des ggT(41,16):

  41 = 16*2 + 9
  16 = 9*1 + 7
   9 = 7*1 + 2
   7 = 2*3 + 1
   2 = 1*2 + 0
  -> ggT(41,16) = 1

Erweiterter Euklidischer Algorithmus:

  1 = 7 - 2*3
    = 7 - (9-7)*3 = 7 - 9*3 + 7*3 = 7*4 - 9*3
    = (16-9)*4 - 9*3 = 16*4 - 9*4 - 9*3 = 16*4 - 9*7
    = 16*4 - (41 - 16*2) * 7 = 16*4 - 41*7 + 16*14
    = 41*(-7) + 16*18
  -> x = -7, y = 18