# Fundamental theorem of arithmetic

In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1 either is prime itself or is the product of prime numbers, and that, although the order of the primes in the second case is arbitrary, the primes themselves are not. For example,

1200 = 24 × 31 × 52 = 3 × 2 × 2 × 2 × 2 × 5 × 5 = 5 × 2 × 3 × 2 × 5 × 2 × 2 = etc.

The theorem is stating two things: first, that 1200 can be represented as a product of primes, and second, no matter how this is done, there will always be four 2s, one 3, two 5s, and no other primes in the product.

The requirement that the factors be prime is necessary: factorizations containing composite numbers may not be unique (e.g. 12 = 2 × 6 = 3 × 4).

## History

Book VII, propositions 30 and 32 of Euclid's Elements is essentially the statement and proof of the fundamental theorem.

If two numbers by multiplying one another make some number, and any prime number measure the product, it will also measure one of the original numbers.

— Euclid, Elements Book VII, Proposition 30

Proposition 30 is referred to as Euclid's lemma. And it is the key in the proof of the fundamental theorem of arithmetic.

Any composite number is measured by some prime number.

— Euclid, Elements Book VII, Proposition 31

Proposition 31 is derived from proposition 30.

Any number either is prime or is measured by some prime number.

— Euclid, Elements Book VII, Proposition 32

Proposition 32 is derived from proposition 31.

Article 16 of Gauss' Disquisitiones Arithmeticae is an early modern statement and proof employing modular arithmetic.

## Applications

### Canonical representation of a positive integer

Every positive integer n > 1 can be represented in exactly one way as a product of prime powers:

$n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}$ where Template:Nowrap beginp1 < p2 < ... < pkTemplate:Nowrap end are primes and the αi are positive integers.

This representation is called the canonical representation of n, or the standard form of n.

For example 999 = 33×37, 1000 = 23×53, 1001 = 7×11×13

Note that factors p0 = 1 may be inserted without changing the value of n (e.g. 1000 = 23×30×53).
In fact, any positive integer can be uniquely represented as an infinite product taken over all the positive prime numbers,

$n=2^{n_{2}}3^{n_{3}}5^{n_{5}}7^{n_{7}}\cdots =\prod p_{i}^{n_{p_{i}}},$ where a finite number of the ni are positive integers, and the rest are zero. Allowing negative exponents provides a canonical form for positive rational numbers.

### Arithmetic operations

This representation is convenient for expressions like these for the product, gcd, and lcm:

$a\cdot b=2^{a_{2}+b_{2}}\,3^{a_{3}+b_{3}}\,5^{a_{5}+b_{5}}\,7^{a_{7}+b_{7}}\cdots =\prod p_{i}^{a_{p_{i}}+b_{p_{i}}},$ $\gcd(a,b)=2^{\min(a_{2},b_{2})}\,3^{\min(a_{3},b_{3})}\,5^{\min(a_{5},b_{5})}\,7^{\min(a_{7},b_{7})}\cdots =\prod p_{i}^{\min(a_{p_{i}},b_{p_{i}})},$ $\operatorname {lcm} (a,b)=2^{\max(a_{2},b_{2})}\,3^{\max(a_{3},b_{3})}\,5^{\max(a_{5},b_{5})}\,7^{\max(a_{7},b_{7})}\cdots =\prod p_{i}^{\max(a_{p_{i}},b_{p_{i}})}.$ While expressions like these are of great theoretical importance their practical use is limited by our ability to factor numbers.

### Arithmetical functions

{{#invoke:main|main}}

Many arithmetical functions are defined using the canonical representation. In particular, the values of additive and multiplicative functions are determined by their values on the powers of prime numbers.

## Proof

The proof uses Euclid's lemma (Elements VII, 30): if a prime p divides the product of two natural numbers a and b, then p divides a or p divides b (or both). That article has a proof of Euclid's lemma (in a nutshell: Euclid's lemma follows from Bézout's identity which in turn follows from Euclid's algorithm.)

### Existence

We need to show that every integer greater than 1 is a product of primes. By induction: assume it is true for all numbers between 1 and n. If n is prime, there is nothing more to prove (a prime is a trivial product of primes, a "product" with only one factor). Otherwise, there are integers a and b, where n = ab and Template:Nowrap begin1 < ab < n.Template:Nowrap end By the induction hypothesis, Template:Nowrap begina = p1p2...pjTemplate:Nowrap end and Template:Nowrap beginb = q1q2...qkTemplate:Nowrap end are products of primes. But then Template:Nowrap beginn = ab = p1p2...pjq1q2...qkTemplate:Nowrap end is a product of primes.

### Uniqueness

Assume that s > 1 is the product of prime numbers in two different ways:

{\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}} We must show m = n and that the qj are a rearrangement of the pi.

By Euclid's lemma, p1 must divide one of the qj; relabeling the qj if necessary, say that p1 divides q1. But q1 is prime, so its only divisors are itself and 1. Therefore, p1 = q1, so that

{\begin{aligned}{\frac {s}{p_{1}}}&=p_{2}\cdots p_{m}\\&=q_{2}\cdots q_{n}.\end{aligned}} Reasoning the same way, p2 must equal one of the remaining qj. Relabeling again if necessary, say p2 = q2. Then

{\begin{aligned}{\frac {s}{p_{1}p_{2}}}&=p_{3}\cdots p_{m}\\&=q_{3}\cdots q_{n}.\end{aligned}} This can be done for each of the m pi's, showing that mn and every pi is a qj. Applying the same argument with the $p$ 's and $q$ 's reversed shows nm (hence m = n) and every qj is a pi.

### Elementary proof of uniqueness

The fundamental theorem of arithmetic can also be proved without using Euclid's lemma, as follows:

Assume that s > 1 is the smallest positive integer which is the product of prime numbers in two different ways. If s were prime then it would factor uniquely as itself, so there must be at least two primes in each factorization of s:

{\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}} If any pi = qj then, by cancellation, s/pi = s/qj would be a positive integer greater than 1 with two distinct factorizations. But s/pi is smaller than s, meaning s would not actually be the smallest such integer. Therefore every pi must be distinct from every qj.

Without loss of generality, take p1 < q1 (if this is not already the case, switch the p and q designations.) Consider

$t=(q_{1}-p_{1})(q_{2}\cdots q_{n}),$ and note that 1 < q2t < s. Therefore t must have a unique prime factorization. By rearrangement we see,

{\begin{aligned}t&=q_{1}(q_{2}\cdots q_{n})-p_{1}(q_{2}\cdots q_{n})\\&=s-p_{1}(q_{2}\cdots q_{n})\\&=p_{1}((p_{2}\cdots p_{m})-(q_{2}\cdots q_{n})).\end{aligned}} Here u = ((p2 ... pm) - (q2 ... qn)) is positive, for if it were negative or zero then so would be its product with p1, but that product equals t which is positive. So u is either 1 or factors into primes. In either case, t = p1u yields a prime factorization of t, which we know to be unique, so p1 appears in the prime factorization of t.

If (q1 - p1) equaled 1 then the prime factorization of t would be all q's, which would preclude p1 from appearing. Thus (q1 - p1) is not 1, but is positive, so it factors into primes: (q1 - p1) = (r1 ... rh). This yields a prime factorization of

$t=(r_{1}\cdots r_{h})(q_{2}\cdots q_{n}),$ which we know is unique. Now, p1 appears in the prime factorization of t, and it is not equal to any q, so it must be one of the r's. That means p1 is a factor of (q1 - p1), so there exists a positive integer k such that p1k = (q1 - p1), and therefore

$p_{1}(k+1)=q_{1}.$ But that means q1 has a proper factorization, so it is not a prime number. This contradiction shows that s does not actually have two different prime factorizations. As a result, there is no smallest positive integer with multiple prime factorizations, hence all positive integers greater than 1 factor uniquely into primes.

## Generalizations

The first generalization of the theorem is found in Gauss's second monograph (1832) on biquadratic reciprocity. This paper introduced what is now called the ring of Gaussian integers, the set of all complex numbers a + bi where a and b are integers. It is now denoted by $\mathbb {Z} [i].$ He showed that this ring has the four units ±1 and ±i, that the non-zero, non-unit numbers fall into two classes, primes and composites, and that (except for order), the composites have unique factorization as a product of primes.

However, it was also discovered that unique factorization does not always hold. An example is given by $\mathbb {Z} [{\sqrt {-5}}]$ . In this ring one has

$6=2\times 3=(1+{\sqrt {-5}})\times (1-{\sqrt {-5}}).$ Examples like this caused the notion of "prime" to be modified. In $\mathbb {Z} [{\sqrt {-5}}]$ it can be proven that if any of the factors above can be represented as a product, e.g. 2 = ab, then one of a or b must be a unit. This is the traditional definition of "prime". It can also be proven that none of these factors obeys Euclid's lemma; e.g. 2 divides neither (1 + √−5) nor (1 − √−5) even though it divides their product 6. In algebraic number theory 2 is called irreducible in $\mathbb {Z} [{\sqrt {-5}}]$ (only divisible by itself or a unit) but not prime in in $\mathbb {Z} [{\sqrt {-5}}]$ (if it divides a product it must divide one of the factors). The mention of $\mathbb {Z} [{\sqrt {-5}}]$ is required because 2 is prime and irreducible in $\mathbb {Z} .$ Similarly, 5 is prime and irreducible in $\mathbb {Z}$ and not prime nor irreducible in $\mathbb {Z} [{\sqrt {-5}}].$ Using these definitions it can be proven that in any ring a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers $\mathbb {Z}$ every irreducible is prime". This is also true in $\mathbb {Z} [i]$ and $\mathbb {Z} [\omega ],$ but not in $\mathbb {Z} [{\sqrt {-5}}].$ The rings where every irreducible is prime are called unique factorization domains. As the name indicates, the fundamental theorem of arithmetic is true in them. Important examples are polynomial rings over the integers or over a field, Euclidean domains and principal ideal domains.

In 1843 Kummer introduced the concept of ideal number, which was developed further by Dedekind (1876) into the modern theory of ideals, special subsets of rings. Multiplication is defined for ideals, and the rings in which they have unique factorization are called Dedekind domains.

There is a version of unique factorization for ordinals, though it requires some additional conditions to ensure uniqueness.