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 a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to the order of the factors. For example,
The theorem says two things for this example: first, that 1200 be represented as a product of primes, and second, that no matter how this is done, there will always be exactly 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.
This theorem is one of the main reasons why 1 is not considered a prime number: if 1 were prime, then factorization into primes would not be unique; for example,

Euclid's original version

Book VII, propositions 30, 31 and 32, and Book IX, proposition 14 of Euclid's Elements are essentially the statement and proof of the fundamental theorem.
Proposition 30 is referred to as Euclid's lemma, and it is the key in the proof of the fundamental theorem of arithmetic.
Proposition 31 is proved directly by infinite descent.
Proposition 32 is derived from proposition 31, and proves that the decomposition is possible.
Book IX, proposition 14 is derived from Book VII, proposition 30, and proves partially that the decomposition is unique – a point critically noted by André Weil. Indeed, in this proposition the exponents are all equal to one, so nothing is said for the general case.
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:
where p1 < p2 <... < pk are primes and the ni 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.
This representation is called the canonical representation of n, or the standard form of n. For example,
Factors p0 = 1 may be inserted without changing the value of n. In fact, any positive integer can be uniquely represented as an infinite product taken over all the positive prime numbers:
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

The canonical representations of the product, greatest common divisor, and least common multiple of two numbers a and b can be expressed simply in terms of the canonical representations of a and b themselves:
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 uses Euclid's lemma : If a prime divides the product of two integers and, then must divide at least one of those integers and.

Existence

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. By the induction hypothesis, and are products of primes. But then 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 = p1 p2... pj = q1 q2... qk, where each pi and qi is prime. We see p1 divides q1 q2... qk, so p1 divides some qi by Euclid's lemma. Without loss of generality, say p1 divides q1. Since p1 and q1 are both prime, it follows that p1 = q1. Returning to our factorizations of n, we may cancel these two terms to conclude p2... pj = q2... qk. We now have two distinct prime factorizations of some integer strictly smaller than n, which contradicts the minimality of n.

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 s is not prime and there must be at least two primes in each factorization of s:
If any pi = qj then, by cancellation, s/pi = s/qj would be another positive integer, different from s, which is greater than 1 and also has 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 Consider
and note that 1 < q2 ≤ t < s. Therefore t must have a unique prime factorization. By rearrangement we see,
Here u = - ) 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 equaled 1 then the prime factorization of t would be all qs, which would preclude p1 from appearing. Thus is not 1, but is positive, so it factors into primes: =. This yields a prime factorization of
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 rs. That means p1 is a factor of, so there exists a positive integer k such that p1k =, and therefore
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 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 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.
Similarly, in 1844 while working on cubic reciprocity, Eisenstein introduced the ring, where is a cube root of unity. This is the ring of Eisenstein integers, and he proved it has the six units and that it has unique factorization.
However, it was also discovered that unique factorization does not always hold. An example is given by. In this ring one has
Examples like this caused the notion of "prime" to be modified. In 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 nor even though it divides their product 6. In algebraic number theory 2 is called irreducible in but not prime in . The mention of is required because 2 is prime and irreducible in 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 every irreducible is prime". This is also true in and but not in
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 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.