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

Aus VoWi
Zur Navigation springen Zur Suche springen

Angabe[Bearbeiten | Quelltext bearbeiten]

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

Lösungsansatz[Bearbeiten | Quelltext bearbeiten]

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
Abgerufen von „https://vowi.fsinf.at/index.php?title=TU_Wien:Algebra_und_Diskrete_Mathematik_UE_(diverse)/Übungen_SS12/Beispiel_44&oldid=89576“