Die Elemente der Zahlentheorie / dargestellt von Paul Bachmann.

22 Erster Abschnitt
während
m =Q + r,
Q ganz, r aber eine der Zahlen 1, 2, 3,... (n- 1), so würde
rh = (q -- Q) * n,
also rh ein Vielfaches von n sein, während doch r < n ist.
So ist der Satz bewiesen: Ein Produkt, dessen einer
Faktor zu n relativ prim ist, kann nur dann durch n
theilbar sein, wenn der andere Faktor dies ist.
Dieser Satz lässt sich umkehren: Wenn ein Produkt
nur dann durch n theilbar sein kann, wenn es der
eine Faktor ist, so ist der andere Faktor relativ prim
zu n. Denn, wäre mh1 nur dann durch n theilbar, wenn m
es ist, und hätten dennoch h, n einen gemeinsamen Theiler
d> 1, sodass, wenn hi = h'd, n = 'd gesetzt wird, ', n'
ganze Zahlen sind, so würde
mht =- d. h'
durch
n -= n'd
theilbar, indem man m = n' also nicht durch n theilbar
wählte, es entstünde also ein Widerspruch.
Aus dem entwickelten Fundamentalsatze fliessen einige
wichtige Folgerungen. Ist h relativ prim zu n, so ist es dies
offenbar auch zu jedem Theiler von nz. Der Fundamentalsatz
giebt also den folgenden: Ein Produkt, dessen einer
Faktor relativ prim ist zu n, kann nur dann einen
Theiler mit n gemeinschaftlich haben, wenn der
andere Faktor ihn hat; oder auch: Sind h und n relativ
prim, so ist jeder gemeinsame Theiler des Produktes
mnh und n auch gemeinsamer Theiler von m und n.
Dies gilt selbstverständlich auch vom grössten gemeinsamen
Theiler der Zahlen mh und n; zugleich ist aber einfach zu
erkennen, dass letzterer dann auch der grösste gemeinsame
Theiler der Zahlen m und n ist.
Und hieraus ferner fliesst der Satz von Euclid: Sind
sowohl h, n, als auch m, n relative Primzahlen, so ist
auch das Produkt 7hm relativ prim zu n.*)
*) Euclides, a. a. 0. 32.