— 7—

kleinſten Erponenten gibt, den ſie in einer dieſer Zahlen hat, und die ſo erhaltenen Potenzen multiplicicrt. 1

Beiſpiel: Die Zahlen.

504= 23. 32 7, 240= 29. 3 8, 864= 25. 38 haben den größten gemein⸗ ſchaftlichen Diviſor 23. 3= 24. d

Aufgabe I. Den größten gemeinſchaftlichen Diviſor zweier Zahlen a und b a zu beſtimmen, die nicht in ihre Primzahlfactoren zerlegt ſind.

1. Fall. Wenn die Zahl h in a aufgeht, ſo iſt ſie, da ſie auch in ſich ſelbſt aufgeht, ein gemeinſchaftlicher Diviſor von a und b; ſie iſt aber auch der größte gemeinſchaftliche Diviſor, weil keine größere Zahl als b in b aufgehen kann.

2. Fall. b geht nicht in a außfßf.

Erhält man bei der Diviſion zweier beliebigen Zahlen« und s einen Quotient und einen Reſt 9, ſo iſt 112

f

G= A&+ 6, 6 9

und man erkennt leicht, daß der größte gemeinſchaftliche Diviſor von und 6 mit dem größten gemeinſchaftlichen Diviſor von 9 und 0 übereinſtimmt.—

Dies vorausgeſetzt, dividiren wir mit b in a, mit dem Reſt c(der kleiner als b iſt) in b, u. ſ. w. und erhalten, da die Reſte immer kleiner werden, alſo endlich einmal der Reſt Null erſcheinen muß, die Gleichungen I dotr

aàa= bq+ b= er+ d f= gu+ h g= hyv.

Da nun die Zahlenpaare a und b, b und c, e und d, u. ſ. w., g und h denſelben größten gemeinſchaftlichen Diviſor haben, und da der größte gemeinſchaftliche Diviſor des letzten Paarsch iſt, ſo iſt h auch der größte gemeinſchaftliche Diviſor von a und b.

Aufgabe II. Den größten gemeinſchaftlichen Diviſor mehrerer Zahlen a, b, c, u. ſ. w. zu beſtimmen, die nicht in ihre Primzahlfactoren zerlegt ſind.

Man ermittle zunächſt den größten gemeinſchaftlichen Diviſor d der beiden Zahlen a und b, und ſodann den größten gemeinſchaftlichen Diviſor d“ von d und c, ſo iſt d“ der größte ge⸗ meinſchaftliche Diviſor der drei Zahlen a, b, c; denn d' geht in c und, weil in d, auch in a und b auf, iſt alſo ein Diviſor von a, b, c. Hätten nun die drei Zahlen a, b, c einen ge⸗ meinſchaftlichen Diviſor D, der größer als d' wäre, ſo würde D in c und, weil in a und b, auch in d aufgehen, d. h. c und d würden einen gemeinſchaftlichen Diviſor D haben, der größer als der größte gemeinſchaftliche Diviſor beider Zahlen iſt. Es muß alſo d' der größte gemeinſchaft⸗ liche Diviſor von a, b, c ſein. Man ſieht leicht, wie man durch wiederholte Anwendung dieſes Verfahrens den größten gemeinſchaftlichen Diviſor beliebig vieler Zahlen beſtimmen kann.

8. Relative Primzahlen. Zwei Zahlen heißen prim zu einander oder rela⸗ tive Primzahlen, wenn ihr größter gemeinſchaftlicher Diviſor die Einheit iſt.

15 und S ſind prim zu einander, 15 und 12 nicht. 62 5

Lehrfatz 1I. Wenn die Zahlen a und b prim zu einander ſind, ſo geht jeder gemein⸗ ſchaftliche Diviſor von ak und b in k auf.„