Ich weiß, dass zu gegebenen a,b∈ℤ die Menge Ma,b:= {ax+by | x,y ∈ℤ} immer der Form Ma,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.
