Hochzusammengesetzte Zahl

Aufbau

Zwei notwendige Eigenschaften hochzusammengesetzter Zahlen ergeben sich aus der Teileranzahlfunktion. Nach dem Fundamentalsatz der Arithmetik ist jede positive natürliche Zahl ${\displaystyle n}$ folgendermaßen aufgebaut:

${\displaystyle n=p_{1}^{c_{1}}\cdot p_{2}^{c_{2}}\cdot \ldots \cdot p_{k}^{c_{k}}}$    mit Primzahlen    ${\displaystyle p_{1}<p_{2}<\dotsb <p_{k},}$

Die Exponenten ${\displaystyle c_{i}}$ sind dabei von null verschiedene natürliche Zahlen. Für ${\displaystyle k=0}$ ergibt sich das leere Produkt ${\displaystyle n=1}$. Die Definition der Teileranzahlfunktion ${\displaystyle d(n)}$ liefert dann die Anzahl der Teiler für natürliche Zahlen:

${\displaystyle d(n)=(c_{1}+1)\cdot (c_{2}+1)\cdot \ldots \cdot (c_{k}+1)}$.

Für hochzusammengesetzte Zahlen folgt aus dieser Formel:

• Die ${\displaystyle k}$ Primzahlen ${\displaystyle p_{i}}$ sind genau die ersten ${\displaystyle k}$ Primzahlen, denn jede ausgelassene Primzahl würde es ermöglichen, ein kleineres ${\displaystyle n}$ mit gleicher Teileranzahl zu konstruieren.
• Die Folge der Exponenten ist absteigend, es gilt ${\displaystyle c_{1}\geq c_{2}\geq \dotsb \geq c_{k}}$. Andernfalls wäre es durch Vertauschung von Exponenten möglich, ein kleineres ${\displaystyle n}$ mit gleicher Teileranzahl zu konstruieren.

Diese beiden Eigenschaften sind zwar notwendig, aber nicht hinreichend. So muss, ausgenommen ${\displaystyle n=4}$ und ${\displaystyle n=36}$, der letzte Exponent ${\displaystyle 1}$ sein.

Beispiel:

${\displaystyle 720=2^{4}\cdot 3^{2}\cdot 5^{1}}$ hat ${\displaystyle (4+1)\cdot (2+1)\cdot (1+1)=30}$ Teiler.

Da jede kleinere Zahl weniger Teiler hat, ist ${\displaystyle 720}$ eine hochzusammengesetzte Zahl.

Es gibt keine ungeraden hochzusammengesetzten Zahlen außer der 1.