Zeigen Sie, dass d der größte gemeinsame Teiler von a und b ist.

Question

Ich weiß, dass zu gegebenen a,b∈ℤ die Menge M_a,b:= {ax+by | x,y ∈ℤ} immer der Form M_a,b= dℤ ist.

"d" ist eine eindeutige positive Zahl d∈ℕ, die von a und b abhängt.

Nun soll ich zeigen, dass d der größte gemeinsame Teiler von a und b ist. 

Wie muss ich an diese Aufgabe heran gehen? Ich stehe momentan wirklich auf dem Schlauch, ich hoffe ihr könnt mir helfen.

Answer 1

 

Ich weiß, dass zu gegebenen a,b∈ℤ die Menge M_a,b:= {ax+by | x,y ∈ℤ} immer der Form M_a,b= dℤ ist.

"d" ist eine eindeutige positive Zahl d∈ℕ, die von a und b abhängt.

Nun soll ich zeigen, dass d der größte gemeinsame Teiler von a und b ist. Dazu ist es eigentlich notwendig, dass a und b > 0 sind. Was man ohne Einschränkung der Allgemeinheit annehmen kann. Ist a oder b < 0, nimmt man -a oder -b. (Fall beide = 0 ist mal ausgeschlossen)

Exkurs:

Wie bestimmt man den ggt von 24 und 18?
24: 18 = 1 Rest 6

18: 6 = 3 Rest 0 → ggt 6                  6 = 1*24 - 1* 18

24 und 15?

24: 15 = 1 Rest 9                                      9=1*24 - 1*15

15: 9 = 1 Rest 6                                        6=1*15 - 1*9

9: 6 = 1 Rest 3                                          3= 1*9 - 1*6

6:3 = 2 Rest 0 ---------> ggt 3                 

 

Restkette rückwärts einsetzen zeigt, dass ggt als x*a + y * b geschrieben werden kann:

  3= 1*9 - 1*6 = 1*9 -1*(1*15 - 1*9) = 

= 1*(1*24 - 1*15) - 1*(1*15 - 1*(1*24 - 1* 15) = x* 24 + y * 15

Hier geht konkret 3 = 2* 24 - 3 *15

Nun musst du das verallgemeinert aufschreiben. Dann ist gezeigt, dass der ggt d als Linearkombination von a und b dargestellt werden kann, d.h.  d = xa + yb. Alle z-fachen davon erhält man als zd = (zx)a + (zy)b 

Es bleibt noch zu zeigen, dass weniger als der ggt (aber nicht 0) nicht erreicht werden kann. 
d sei der ggt von a und b,
dann gibt es ein c und ein e so dass gilt: a=dc und b=de
Nun ist xa + yb = xdc + yde = d(xc + ye) also immer durch d teilbar (oder 0) qed.