ggt beweis

19/03/2008 - 15:44 von Bernd Schneider | Report spam
Hi,

ich suche nach einem kurzen Beweis für die folgende Aussage:
Wenn ggT(a,b)=1 dann existieren x,y so dass xa+yb=1.

Mir ist klar, dass man dass bei der Berechnung des ggT mit Hilfe des
euklidischen Algorithmus leicht nachvollziehen kann, aber gibt es dafür
auch einen einfachen Beweis?

Grüße und danke,
Bernd
 

Lesen sie die antworten

#1 Rainer Rosenthal
19/03/2008 - 16:24 | Warnen spam
Bernd Schneider schrieb:
Hi,

ich suche nach einem kurzen Beweis für die folgende Aussage:
Wenn ggT(a,b)=1 dann existieren x,y so dass xa+yb=1.



Bitte korrekt formulieren: dann existieren /ganze Zahlen/ x und y,
so dass ...


Mir ist klar, dass man das bei der Berechnung des ggT mit Hilfe des
euklidischen Algorithmus leicht nachvollziehen kann, aber gibt es dafür
auch einen einfachen Beweis?



Ich habe mir eben Folgendes ausgedacht: Wir nehmen mal a < b an
und betrachten die Vielfachen a, 2a, 3a, 4a, ... von a, indem
wir sie im Gitter 0,1,2,...,b-1 herumlaufen lassen.

Beispiel a=5, b=8:

+--+--+--+--+--+--+--+ Die Rennbahn 0,1,2,...,b-1.
0 1 2 3 4 5 6 7

1
+--+--+--+--+--+--+--+ a = 5 startet bei 1*5.
0 1 2 3 4 5 6 7

2 1
+--+--+--+--+--+--+--+ a geht weiter zu 2*a (modulo 8).
0 1 2 3 4 5 6 7 2*a = 10 ist 2 (mod 8).

2 1 3
+--+--+--+--+--+--+--+ a geht noch weiter zu 3*a.
0 1 2 3 4 5 6 7 3*a = 15 ist 7 (mod 8)

Hier kann man aufhören, weil ja 3*5 + 1 = 2*8 ist. Damit hat
man x=-3 und y=2 gefunden mit xa+yb=1.

Man kann aber auch noch weiter laufen, bis man Platz 1 erreicht:

2 4 1 3
+--+--+--+--+--+--+--+ a geht noch weiter zu 4*a.
0 1 2 3 4 5 6 7 4*a = 20 ist 4 (mod 8)

5 2 4 1 3
+--+--+--+--+--+--+--+ a geht noch weiter zu 5*a.
0 1 2 3 4 5 6 7 5*a = 25 ist 1 (mod 8)

Hier hat man dann 5*5 = 3*8 + 1. Das liefert x=5 und y=-3 mit
xa+yb=1.

Gut zu sehen: mit 6*a und 7*a besetzt man die letzten freien Plàtze,
bevor man bei Platz 0 landet.

Was das Beispiel zeigt:

Wegen der Teilerfremdheit wird a erst nach b Schritten auf
dem Platz 0 landen und vorher keinen Platz doppelt besucht haben.
Also muss es ein ganzes x < b geben, so dass x*a = 1 (mod b)
ist. Dann ist aber x*a = 1 + k*b mit ganzer Zahl k. Mit y = -k
hat man also: xa+yb=1.

Gruss,
Rainer Rosenthal

Ähnliche fragen