§ 11A. Gemeinschaftliche Teiler mehrerer Zahlen.
53
III.
a — hm +
h = \m x + h 2 ,
\ + & 3>
& v _ 2 = h v _ x - m v _ 1 + h v ,
Die letzte Gleichung lehrt, daß h v Teiler von h v _ x ist. Aus der
vorletzten folgt unter Benutzung der Sätze I. und II. dieses Para
graphen, daß h v auch Teiler von & r _ 2 usw., aus der zweiten, daß h v
Teiler von h, aus der ersten endlich, daß h v auch Teiler von a, also
gemeinschaftlicher Teiler von a und h ist. Andererseits ergibt sich
aus der ersten Gleichung der Kette, daß jeder gemeinschaftliche Teiler
von a und b auch Teiler von h x , aus der zweiten, daß jeder gemein
schaftliche Teiler von h und h x auch Teiler von & 2 usw., schließlich
aus der vorletzten, daß jeder gemeinschaftliche Teiler von &„_ 2 und
h v _ x auch Teiler von b v ist. Demnach ist jeder gemeinschaftliche
Teiler von a und h auch Teiler von h v . Aus den beiden Ergebnissen,
daß die Zahl h v erstens gemeinschaftlicher Teiler von a und h und
zweitens ein Vielfaches jedes gemeinschaftlichen Teilers von a, h ist,
folgt weiter, daß h v der größte gemeinschaftliche Teiler von
a und h sein muß. Jeder gemeinschaftliche Teiler zweier Zahlen
ist also Teiler des größten gemeinschaftlichen Teilers dieser Zahlen.
Dann und nur dann, wenn h v = 1, sind a und h relativ prim.
Für zwei solche teilerfremde Zahlen a, h gilt der folgende wichtige Satz:
IV. Wenn a, h relativ prim sind und 1t eine beliebige
Zahl bedeutet, so ist jeder gemeinschaftliche Teiler von a-k
und h auch gemeinschaftlicher Teiler von k und h.
Zum Beweise denken wir uns die Gleichungskette III für h v = 1
aufgeschrieben und jede Gleichung mit k multipliziert:
ak = hmk -f h x k,
hk = h x m x k -f- h 2 k,
b v _ 2 k = h v _ 1 m v _ i k + k.
Aus dieser Kette ergibt sich mittelst derselben Schlüsse, die wir
soeben auf III angewendet haben, unmittelbar der zu beweisende Satz.
Zwei spezielle Fälle desselben seien ihrer Wichtigkeit wegen
besonders hervorgehoben.
IVa. Wenn a, h relativ prim sind und a-k durch h teil
bar ist, so muß k durch h teilbar sein.
