Fundamental theorem of 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

${\displaystyle n=p_1^{n_1}{p}_2^{n_2}\cdots p_k^{n_k}=\prod _{i=1}^k{p}_i^{n_i},}$

where p₁ < p₂ < ... < p_k are primes and the n_i are positive integers. This representation is commonly extended to all positive integers, including 1, by the convention that the empty product is equal to 1 (the empty product corresponds to k = 0).

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

999 = 3³×37,

1000 = 2³×5³,

1001 = 7×11×13.

Factors p⁰ = 1 may be inserted without changing the value of n (for example, 1000 = 2³×3⁰×5³). In fact, any positive integer can be uniquely represented as an infinite product taken over all the positive prime numbers, as

${\displaystyle n=2^{n_1}{3}^{n_2}{5}^{n_3}{7}^{n_4}\cdots =\prod _{i=1}^{\mathrm{\infty }}{p}_i^{n_i},}$

where a finite number of the n_i are positive integers, and the others are zero.

Allowing negative exponents provides a canonical form for positive rational numbers.

Arithmetic operations

The canonical representations of the product, greatest common divisor (GCD), and least common multiple (LCM) of two numbers a and b can be expressed simply in terms of the canonical representations of a and b themselves:

${\displaystyle \begin{array}{rlrl}a\cdot b& =2^{a_1+b_1}{3}^{a_2+b_2}{5}^{a_3+b_3}{7}^{a_4+b_4}\cdots & & =\prod p_i^{a_i+b_i},\\ gcd(a,b)& =2^{min(a_1,b_1)}{3}^{min(a_2,b_2)}{5}^{min(a_3,b_3)}{7}^{min(a_4,b_4)}\cdots & & =\prod p_i^{min(a_i,b_i)},\\ \mathrm{lcm}(a,b)& =2^{max(a_1,b_1)}{3}^{max(a_2,b_2)}{5}^{max(a_3,b_3)}{7}^{max(a_4,b_4)}\cdots & & =\prod p_i^{max(a_i,b_i)}.\end{array}}$

However, integer factorization, especially of large numbers, is much more difficult than computing products, GCDs, or LCMs, so these formulas have limited use in practice.

Arithmetic functions

Many arithmetic 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 of uniqueness uses Euclid's lemma (Elements VII, 30): If a prime divides the product of two integers, then it must divide at least one of these integers.

Existence

It must be shown that every integer greater than 1 is either prime or a product of primes. Let n be an integer greater than 1 and make the inductive assumption that every integer greater than 1 and less than n is either prime or a product of primes. If n is prime, there is nothing more to prove. Otherwise, there are integers a and b, where n = a b, and 1 < a ≤ b < n. By the inductive hypothesis, a = p₁ p₂ ⋅⋅⋅ p_j and b = q₁ q₂ ⋅⋅⋅ q_k are products of primes. But then n = a b = p₁ p₂ ⋅⋅⋅ p_j q₁ q₂ ⋅⋅⋅ q_k is a product of primes.

Uniqueness

Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Let n be the least such integer and write n = p₁ p₂ ... p_j = q₁ q₂ ... q_k, where each p_i and q_i is prime. We see that p₁ divides q₁ q₂ ... q_k, so p₁ divides some q_i by Euclid's lemma. Without loss of generality, say p₁ divides q₁. Since p₁ and q₁ are both prime, it follows that p₁ = q₁. Returning to our factorizations of n, we may cancel these two factors to conclude that p₂ ... p_j = q₂ ... q_k. We now have two distinct prime factorizations of some integer strictly smaller than n, which contradicts the minimality of n.

Uniqueness without Euclid's lemma

The fundamental theorem of arithmetic can also be proved without using Euclid's lemma The proof that follows is inspired by Euclid's original version of the Euclidean algorithm.

Assume that ${\displaystyle s}$ is the smallest positive integer which is the product of prime numbers in two different ways. Incidentally, this implies that ${\displaystyle s}$, if it exists, must be a composite number greater than ${\displaystyle 1}$. Now, say

${\displaystyle \begin{array}{cc}s& =p_1{p}_2\cdots p_m\\ & =q_1{q}_2\cdots q_n.\end{array}}$

Every ${\displaystyle p_i}$ must be distinct from every ${\displaystyle q_j.}$ Otherwise, if say ${\displaystyle p_i=q_j,}$ then there would exist some positive integer ${\displaystyle t=s/p_i=s/q_j}$ that is smaller than s and has two distinct prime factorizations. One may also suppose that ${\displaystyle p_1<q_1,}$ by exchanging the two factorizations, if needed.

Setting ${\displaystyle P=p_2\cdots p_m}$ and ${\displaystyle Q=q_2\cdots q_n,}$ one has ${\displaystyle s=p_{1}P=q_{1}Q.}$ Also, since ${\displaystyle p_1<q_1,}$ one has ${\displaystyle Q<P.}$ It then follows that

${\displaystyle s-p_{1}Q=(q_1-p_1)Q=p_1(P-Q)<s.}$

As the positive integers less than s have been supposed to have a unique prime factorization, ${\displaystyle p_1}$ must occur in the factorization of either ${\displaystyle q_1-p_1}$ or Q. The latter case is impossible, as Q, being smaller than s, must have a unique prime factorization, and ${\displaystyle p_1}$ differs from every ${\displaystyle q_j.}$ The former case is also impossible, as, if ${\displaystyle p_1}$ is a divisor of ${\displaystyle q_1-p_1,}$ it must be also a divisor of ${\displaystyle q_1,}$ which is impossible as ${\displaystyle p_1}$ and ${\displaystyle q_1}$ are distinct primes.

Therefore, there cannot exist a smallest integer with more than a single distinct prime factorization. Every positive integer must either be a prime number itself, which would factor uniquely, or a composite that also factors uniquely into primes, or in the case of the integer ${\displaystyle 1}$, not factor into any prime.

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 ${\displaystyle \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 the composites have unique factorization as a product of primes (up to the order and multiplication by units).

Similarly, in 1844 while working on cubic reciprocity, Eisenstein introduced the ring ${\displaystyle \mathbb{Z}[\omega ]}$, where $\omega =\frac{-1+\sqrt{-3}}{2}$ is a cube root of unity (that is, ${\displaystyle {\omega }^3=1}$). This is the ring of Eisenstein integers, and he proved it has the six units ${\displaystyle \pm 1,\pm \omega ,\pm {\omega }^2}$ and that it has unique factorization.

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

${\displaystyle 6=2\cdot 3=\left(1+\sqrt{-5}\right)\left(1-\sqrt{-5}\right).}$

Examples like this caused the notion of "prime" to be modified. In ${\displaystyle \mathbb{Z}\left[\sqrt{-5}\right]}$ it can be proven that if any of the factors above can be represented as a product, for example, 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; for example, 2 divides neither ${\displaystyle (1+\sqrt{-5})}$ nor ${\displaystyle (1-\sqrt{-5})}$ even though it divides their product 6. In algebraic number theory 2 is called irreducible in ${\displaystyle \mathbb{Z}\left[\sqrt{-5}\right]}$ (only divisible by itself or a unit) but not prime in ${\displaystyle \mathbb{Z}\left[\sqrt{-5}\right]}$ (if it divides a product it must divide one of the factors). The mention of ${\displaystyle \mathbb{Z}\left[\sqrt{-5}\right]}$ is required because 2 is prime and irreducible in ${\displaystyle \mathbb{Z}.}$ Using these definitions it can be proven that in any integral domain a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers ${\displaystyle \mathbb{Z}}$ every irreducible is prime". This is also true in ${\displaystyle \mathbb{Z}[i]}$ and ${\displaystyle \mathbb{Z}[\omega ],}$ but not in ${\displaystyle \mathbb{Z}[\sqrt{-5}].}$

The rings in which factorization into irreducibles is essentially unique are called unique factorization domains. 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.

Any commutative Möbius monoid satisfies a unique factorization theorem and thus possesses arithmetical properties similar to those of the multiplicative semigroup of positive integers. Fundamental Theorem of Arithmetic is, in fact, a special case of the unique factorization theorem in commutative Möbius monoids.