Fundamental theorem of arithmetic

In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors.[3][4][5] For example,

The theorem says two things about this example: first, that 1200 can 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.

This theorem generalizes to other algebraic structures, in particular to polynomial rings over a field. These structures are called unique factorization domains.

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.

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.

(In modern terminology: if a prime p divides the product ab, then p divides either a or b or both.) Proposition 30 is referred to as Euclid's lemma, and it is the key in the proof of the fundamental theorem of arithmetic.

(In modern terminology: every integer greater than one is divided evenly by some prime number.) Proposition 31 is proved directly by infinite descent.

Proposition 32 is derived from proposition 31, and proves that the decomposition is possible.

If a number be the least that is measured by prime numbers, it will not be measured by any other prime number except those originally measuring it.

(In modern terminology: a least common multiple of several prime numbers is not a multiple of any other prime number.) 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.[6] 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.[1]

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 (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,

Factors p0 = 1 may be inserted without changing the value of n (for example, 1000 = 23×30×53). 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.

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:

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.

The proof 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.

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 < ab < n. By the induction hypothesis, a = p1 p2 ⋅⋅⋅ pj and b = q1 q2 ⋅⋅⋅ qk are products of primes. But then n = a b = p1 p2 ⋅⋅⋅ pj q1 q2 ⋅⋅⋅ qk 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 = p1 p2 ... pj = q1 q2 ... qk, where each pi and qi is prime. We see that 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 factors to conclude that p2 ... pj = q2 ... qk. 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.

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.

The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

The two monographs Gauss published on biquadratic reciprocity have consecutively numbered sections: the first contains §§ 1–23 and the second §§ 24–76. Footnotes referencing these are of the form "Gauss, BQ, § n". Footnotes referencing the Disquisitiones Arithmeticae are of the form "Gauss, DA, Art. n".

These are in Gauss's Werke, Vol II, pp. 65–92 and 93–148; German translations are pp. 511–533 and 534–586 of the German edition of the Disquisitiones.