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[8] of n, or the standard form[9][10] 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 = ab, 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 = ab = p₁p₂...p_jq₁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. (Note j and k are both at least 2.) We see 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 terms to conclude 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, 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 s is not prime and there must be at least two primes in each factorization of s:

${\displaystyle {\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}}$

If any p_i = q_j then, by cancellation, s/p_i = s/q_j would be another positive integer, different from s, which is greater than 1 and also has two distinct factorizations. But s/p_i is smaller than s, meaning s would not actually be the smallest such integer. Therefore every p_i must be distinct from every q_j.

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

${\displaystyle t=(q_{1}-p_{1})(q_{2}\cdots q_{n}),}$

and note that 1 < q₂ ≤ t < s. Therefore t must have a unique prime factorization. By rearrangement we see,

${\displaystyle {\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 = ((p₂ ... p_m) - (q₂ ... q_n)) is positive, for if it were negative or zero then so would be its product with p₁, but that product equals t which is positive. So u is either 1 or factors into primes. In either case, t = p₁u yields a prime factorization of t, which we know to be unique, so p₁ appears in the prime factorization of t.

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

${\displaystyle t=(r_{1}\cdots r_{h})(q_{2}\cdots q_{n}),}$

which we know is unique. Now, p₁ 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 p₁ is a factor of (q₁ - p₁), so there exists a positive integer k such that p₁k = (q₁ - p₁), and therefore

${\displaystyle p_{1}(k+1)=q_{1}.}$

But that means q₁ 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.