Fundamental theorem of arithmetic

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[7] of n, or the standard form[8][9] 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:

${\displaystyle n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}},}$

where a finite number of the n_i are positive integers, and the rest are zero. Allowing negative exponents provides a canonical form for positive rational numbers.

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{alignedat}{2}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})},\\\operatorname {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{alignedat}}}$

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.

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.

It must be shown that every integer greater than 1 is either prime or a product of primes. First, 2 is prime. Then, by strong induction, assume this is true for all numbers greater than 1 and less than n. 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 induction 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.

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.

The fundamental theorem of arithmetic can also be proved without using Euclid's lemma.[10] 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{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}}$

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.