Fundamental Theorem of Arithmetic (Part I: Introduction)

Basic Concept

The Fundamental Theorem of Arithmetic – also known as Unique Factorization of Integers Theorem1 and Prime Factorization Theorem – basically states that every integer greater than \( 1 \) is either itself a prime number or can be decomposed in its prime factors in a unique way, where the uniqueness does not necessarily cover the order of the factors. A prime number or simply a prime is a natural number that has only two trivial divisors, namely the number itself and \(1\). The order of the factors does not matter due to the commutative property of multiplication that holds within the set of integers (\( \forall \; a, b \in \mathbb{Z}\), \(a \cdot b = b \cdot a \)). For example, \(78 = 2 \cdot 3 \cdot 13 = 13 \cdot 2 \cdot 3\). From this point of view, one can see the primes as some sort of fundamental buildings blocks from which all other integers can be made – the “atoms“ so to speak.2

Historical Notes

In the mathematical literature it is said that this theorem must have been already known to Euclid (fl. 300 BC)3, but that it has been stated precisely only in 1801 by Carl Friedrich Gauss (1777-1855).4 Indeed, in his work on the theory of numbers named Disquisitiones Arithmeticae, Carl Friedrich Gauss gets to the conclusion that:

A composite number can be resolved into prime factors in only one way.

Gauß, C. F. & Clarke, A. A. Disquisitiones arithmeticae.5

Necessity of a proof

Now, one could think that this is all so obvious that no mathematical proof is needed. But this would not be very accurate. In fact, just beginning to decompose an integer into primes does not guarantee that a number could not have more than one genuinely different prime factorizations: Imagine for example that one successively divides the number by the largest prime factor instead of the smallest prime factor; is it really excluded that this would not give a completely different set of primes?6 This uncertainty arises especially when the integer to be factorized is very large.

In the continuation of this post (Part II) we will see different approaches to proving the Fundamental Theorem of Arithmetic. Stay tuned…


Gowers, T. The Princeton Companion to Mathematics. (Princeton university press, Princeton, 2008).
Gauß, C. F. & Clarke, A. A. Disquisitiones Arithmeticae. (Yale Univ.Pr, New Haven, 1966).
Kline, M. Mathematical Thought from Ancient to Modern Times. (Oxford University Press, New York, 1990).
Burton, D. M. Elementary Number Theory. (McGraw-Hill, Boston, 2002).
Epp, S. S. Discrete Mathematics: With Applications. (Cengage, Australia, 2020).