Die Elemente der Zahlentheorie / dargestellt von Paul Bachmann.

]8 Erster Abschnitt
in dem Bruche - enthalten ist. Die Zahl r dagegen heisst
der Rest der Zahl Ia (mod.n).
Sind in, rn' zwei verschiedene Vielfache von n,
imn qn, m'= q'n,
so heisst n ein gemeinschaftlicher Theiler von in, n'.
Da jede ganze Zahl als ein Vielfaches der Einheit angesehen
werden kann, so haben zwei Zahlen en, m' jedenfalls die Eins
zum gemeinschaftlichen Theiler. Haben sie aber ausser diesem
selbstverständlichen Theiler keinen andern gemeinsamen
Theiler, als dessen Vielfache sie dargestellt werden können,
so nennt man sie zwei Zahlen ohne gemeinsamen
Theiler oder besser: relative Primzahlen.
Jeder Theiler einer Zahl in ist numerisch kleiner als sie
selbst, es sei denn, dass man, wie es allerdings meist geschieht, auch die Zahl m selbst als einen ihrer Theiler:
m =1 * nm, auffasst.
Da es nun unterhalb einer Zahl m in der natürlichen
Zahlenreihe nur eine endliche Menge ganzer Zahlen giebt,
desgleichen unterhalb einer Zahl m', so ist einleuchtend,
dass es unter den gemeinsamen Theilern von m und
wm einen grössten gemeinsamen Theiler d geben muss.
Setzt man dann
n = t. d, mn'== — ' d,
so sind /i, ei' zwei ganze Zahlen ohne gemeinsamen
Theiler oder relativ prim, Denn, hätten sie einen von 1
verschiedenen Theiler d' gemeinsam, sodass
ee ee, e,,' v' d'
gesetzt werden kann, unter v, v' zwei ganze Zahlen verstanden, so würden
in-==v d'd, m'= v'. d'c,
d.h. nh, Im' hätten den gemeinsamen Theiler d'd, der ein
Vielfaches von d, also grösser wäre als d, gegen die Voraussetzung.
2. Schreibt man unter die Zahlenreihe (1) die Reste,
welche die einzelnen Zahlen in Bezug auf eine willkürlich gewählte Zahl n lassen, so sieht man die Reihe der Zahlen