84

Allgemeine Arithmetik.

Der letzte von o verschiedene Rest L der gefundenen Reihe ist dergrößte gemeinschaftliche Divisor der Zahlen a und ö. DennH ist ein Divisor von §-, also auch (2) von kA -f- d. i. /, also auchvon jedem vorangehenden Rest, sowie endlich von L und «. Umgekehrtschließt man, daß ein Divisor von « und L auch ein Divisor von e, ä,

. . , ^ ist, und daher nicht mehr als ä sein kann.

Wenn zwei Zahlen einen gemeinschaftlichen Divisor über 1 nichthaben, so heißen sie prim zu einander (xrimi intsr so, relative Prim-zahlen). Wenn L der größte gemeinschaftliche Divisor von « und ö ist,so sind die Zahlen,« : und S : prim zu einander. Insbesonderesind je zwei aufeinander folgende natürliche Zahlen, « und « -f- 1, re-lative Primzahlen. Luol. VII, 1.

Anmerkung. Wenn der Zähler und der Nenner eines Bruchsnicht prim zu einander sind, so ist der Bruch reductibel und erhältseinen einfachsten Ausdruck, indem Zähler und Nenner durch ihren größ-ten gemeinschaftlichen Divisor dividirt werden (tz. II, 2). Wenn Zäh-ler und Nenner relative Primzahlen sind, so ist der Bruch irreduc-t i b e l.

Um den größten gemeinschaftlichen Divisor mehrerer Zahlen «, ö, e,. . zu finden, berechnet man den größten gemeinschaftlichen Divisor Hvon « und L, den größten gemeinschaftlichen Divisor von L und e,u. s. w. Jede Zahl, welche in «, L einzeln aufgeht, ist ein Divisor vonjede Zahl, welche in «, S, e einzeln aufgeht, ist ein gemeinschaftlicherDivisor von ä und o, also ein Divisor von H', u. s. w.

H. Wenn « und S prim zu einander sind, so geht jeder gemein-schaftliche Divisor von «L und L in L auf, und wenn zugleich «!' durchL theilbar ist, so ist K durch L theilbar.

Beweis. Unter der Voraussetzung, daß « prim zu ö ist, wirdin der Kette von Gleichungen (3) der letzte Rest H -- I, folglich

-s- ei'

-f- IÄ:

-si 1^.

Hieraus schließt man (2), daß ein gemeinschaftlicher Divisor von «Lund b in ei-, cU-, . ., I- aufgeht. Ebenso schließt man, wenn «I- durchö theilbar ist, daß L in «L, c/L, . . , I- aufgeht.

3. Die gemeinschaftlichen Dividuen von « und ö d. h. die Zah-len, welche sowohl durch « als auch durch ö theilbar sind, sind von der

Form a wenn durch ä der größte gemeinschaftliche Divisor von