§ 11C. Darstellung einer beliebigen Zahl als Produkt von Primzahlen. 57 
bar ist. Es kann 
prim sein (nach, 
er 1 noch einen 
ie identisch. Ein 
Läßt man den 
it auf die übrig- 
nt man, daß ein 
Die Fortsetzung 
ler rechten Seite 
gleich dem Pro- 
B. Da aber die 
m selbstverständ- 
ahlen p, p' } p" } .., 
reinstimmt, eine 
rt als Produkt 
Faktor auftreten. 
imzahlen als Po- 
i die Darstellung 
Primzahlen und 
a in ihre Prim 
eine solche Zahl 
Gierigkeiten. Bis 
1s zu prüfen, ob 
ihlen teilbar ist, 
nn nicht gleich- 
[ethoden, welche 
ingehen, weil sie 
x ) Man besitzt 
sen Grenzen hin 
man auch in 
auf eine letzte 
Primzahl stößt, so daß keine Zahl, die größer als diese ist, Primzahl 
sein könnte, war schon Euklid (Elemente, Buch IX, Nr. XX) be 
kannt. Bedeutet p irgend eine Primzahl, so bilde man das Produkt 
2 • 3 • 5 • • • p aller Primzahlen, die < p, und füge zu diesem Produkte 
1 hinzu. Die so entstandene Zahl läßt bei der Division durch irgend 
eine der Primzahlen 2, 3, 5, ... p den Rest 1, ist also durch keine von 
ihnen teilbar. Es sind jetzt nur zwei Möglichkeiten denkbar: entweder 
ist die Zahl selbst Primzahl, oder sie ist durch eine von 2, 3, 5, ... p 
verschiedene Primzahl teilbar. 1 ) Auf jeden Fall also gibt es, wie 
groß p auch gewählt war, eine noch größere Primzahl. 
Aus der Eindeutigkeit der Zerlegung einer Zahl a in ihre Prim 
faktoren ergibt sich, daß irgend ein Teiler von a keine andern Prim 
faktoren haben kann als a selber und auch keinen in einer höheren 
Potenz. Jeder Teiler von a ist also von der Form 
Pi'P'i* ’ ‘ ' Pn n > w0 0 < h v < a v (v = 1, 2, . . . n), 
und die Anzahl der sämtlichen Teiler von a (1 und a eingeschlossen) 
beträgt (a t + l)(a, + 1) . .. («„ + !)• 
Dementsprechend enthält irgend ein Vielfaches von a notwendig 
jeden Primfaktor von a, und zwar jeden in derselben oder einer 
höheren Potenz von a, ist also von der Form p^ ■ p• • • p n *n • q, wo 
K ^ a v v = 2,... n und q relativ prim zu a. 
Auf Grund dieser Bemerkung können wir für die schon in A. 
und B. gelösten Aufgaben, zu mehreren Zahlen einerseits den größten 
gemeinschaftlichen Teiler, andrerseits das kleinste gemeinschaftliche 
Vielfache zu bestimmen, jetzt noch eine andere Lösung mitteilen, die 
meist vorzuziehen ist, falls man die Zerlegung der gegebenen Zahlen 
in Primfaktoren kennt. 
Um den größten gemeinschaftlichen Teiler zu finden, versieht 
man jede Primzahl, die in jeder der gegebenen Zahlen enthalten ist, 
mit dem Exponenten, welcher ihr in der Primzahlzerlegung derjenigen 
gegebenen Zahl zukommt, in welcher sie am wenigsten oft auftritt. 
Das Produkt der so bestimmten Primzahlpotenzen ist ein Teiler jeder 
der gegebenen Zahlen, während es in mindestens einer der gegebenen 
Zahlen nicht mehr enthalten wäre, sobald man es noch mit irgend 
einer Primzahl multiplizierte; es ist also der gesuchte größte gemein 
schaftliche Teiler. 
Um das kleinste gemeinschaftliche Vielfache zu finden, versehe 
2. Teil, S. 576. 
s 1020000); J. Chr. 
4—1817; Z. Dase, 
. Glaisher, Fac- 
1) Der erste Fall tritt beispielsweise ein für p = 2, 3, 5, 7, 11, der zweite 
für p = 13. 
(2 • 3 • 5 • 7 • 11 • 13 + 1 == 30031 = 59 ■ 509). 
Vgl. Legendre, Zahlentbeorie, übersetzt von Maser, Leipzig 1886, Bd. I, S. 15.