Der Fundamentalsatz der Arithmetik besagt, dass jede natürliche Zahl eine Primfaktorzerlegung besitzt und dass diese bis auf die Reihenfolge der Faktoren eindeutig ist.

Zum ersten Mal vollständig und korrekt bewiesen findet sich der Fundamentalsatz der Arithmetik in der Disquisitiones Arithmeticae von Carl Friedrich Gauß. Er war aber bereits - wenn auch in leicht abgewandelter Form - Euklid bekannt.

Bemerkenswert ist, dass der Beweis der Eindeutigkeit der Zerlegung nicht ohne die additive Struktur der natürlichen Zahlen auskommen kann. Ein Beispiel, aus dem hervorgeht, warum dies so ist, geht auf David Hilbert zurück: Betrachtet man die Menge

der "Hilbert-Zahlen", so könnte man jeden Beweis der Eindeutigkeit in den natürlichen Zahlen, der nur auf Multiplikation beruht, auf diese Zahlen übertragen. In H ist aber die Zerlegung nicht eindeutig, da zum Beispiel 100 = 25·4 = 10·10 ist. Man beachte, dass 4, 10 und 25 alles "Hilbert-Primzahlen" sind, da sie in H nicht weiter zerlegt werden können. (Hinweis: Die in diesem Absatz benutzte Bezeichnung "Hilbert-(Prim)Zahl" wurde nur der einfacheren Erklärung wegen eingeführt und ist nicht mathematisches Allgemeingut.)