Nochmal ggt

20/03/2008 - 15:38 von Bernd Schneider | Report spam
Hi,

nochmal habe ich eine vermutlich ganz leichte Frage zur Berechnung des ggt.
Wieso gilt:
ggT(x,y) = ggt(ay+b,y) = ggt(b,y)

Also wieso ist der ggt von x und y gleich dem ggt von b und y, wobei b der
Rest von x mod y ist?

Gruss,
Bernd
 

Lesen sie die antworten

#1 Joachim Mohr
21/03/2008 - 07:57 | Warnen spam
Bernd Schneider schrieb:
Hi,

nochmal habe ich eine vermutlich ganz leichte Frage zur Berechnung des ggt.
Wieso gilt:
ggT(x,y) = ggt(ay+b,y) = ggt(b,y)

Also wieso ist der ggt von x und y gleich dem ggt von b und y, wobei b der
Rest von x dividiert(!) y ist?



Behaupting: ggT(x,y) = ggT(x mod y,y)

Beweis:
Du gehst also davon aus:

x= ay+b mit b < y (alles in ganzen Zahlen)


Setze
x= p*u
y= q*u
=> b=(p-q)*u
Den Rest überlasse ich Dir.

MFG Joachim

Joachim Mohr Tübingen
http://www.joachimmohr.de/neu.html

Ähnliche fragen