Die Elemente der Zahlentheorie / dargestellt von Paul Bachmann.

44 Erster Abschnitt: Von der Theilbarkeit der Zahlen.
(28) O (n, 1) + (,n, d) + Q(n, d') +.* + u(n,,),
welche nach (27) der Summe
y(n) + +(d) +- (P) + - - + + g(1)
gleich ist, auch gleich der Summe
q(l1) + ((d) + ((d') +- + (n).
Indem wir aber alle Zahlen 1, 2, 3,... n in Gruppen theilen,
in dieselbe Gruppe nämlich alle diejenigen von ihnen vereinigen, welche denselben grössten gemeinsamen Theiler haben
mit n, kommt offenbar jede Zahl in eine ganz bestimmte
Gruppe, und die Anzahl der vertheilten Zahlen, n: ist gleich
der Summe der Mengen, welche in den einzelnen Gruppen
befindlich sind und durch die einzelnen Glieder des Ausdrucks
(28) bestimmt werden. Nach alle diesem findet sich die
Gleichung
(29) F(1) + (d) + (d') +.. + g,(,) =,
für jedes ganzzahlige n, und nunmehr durch Anwendung der
Formel (26) der Werth für cp(n). Die Anzahl derjenigen
Zahlen, welche positiv und nicht grösser als n und
relativ prim sind zu n, beträgt hiernach:
(n) = -- n + n y n +
(I) (n ) (Ill)
was offenbar dasselbe ist, wie
(30) p (n) - (l- )(- )(- )
wenn p, p', ",... die verschiedenen Primzahlen bedeuten, aus denen n besteht.
Ist insbesondere n selbst eine Primzahl p, so ergiebt sich
(30 a) p(p) = - l;
und, ist's eine Primzahlpotenz, n pa, so hat man
(30b) 95(pa) -pa - I-1 - p 1(p -- 1).