Fundamental theorem of arithmetic

File:Disqvisitiones-800.jpg

In Disquisitiones Arithmeticae (1801) Gauss proved the unique factorization theorem<ref name="Gauss1801.loc=16">Template:Harvtxt</ref> and used it to prove the law of quadratic reciprocity.<ref>Template:Harvtxt</ref>

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.<ref>Template:Harvtxt</ref><ref>Template:Harvtxt</ref><ref>Template:Harvtxt</ref> For example,

<math>

1200 = 2^4 \cdot 3^1 \cdot 5^2 = (2 \cdot 2 \cdot 2 \cdot 2) \cdot 3 \cdot (5 \cdot 5) = 5 \cdot 2 \cdot 5 \cdot 2 \cdot 3 \cdot 2 \cdot 2 = \ldots </math>

The theorem says two things about this example: first, that 1200 Template:Em 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 (for example, <math>12 = 2 \cdot 6 = 3 \cdot 4</math>).

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, <math>2 = 2 \cdot 1 = 2 \cdot 1 \cdot 1 = \ldots</math>

The theorem generalizes to other algebraic structures that are called unique factorization domains and include principal ideal domains, Euclidean domains, and polynomial rings over a field. However, the theorem does not hold for algebraic integers.<ref>In a ring of algebraic integers, the factorization into prime elements may be non unique, but one can recover a unique factorization if one factors into ideals.</ref> This failure of unique factorization is one of the reasons for the difficulty of the proof of Fermat's Last Theorem. The implicit use of unique factorization in rings of algebraic integers is behind the error of many of the numerous false proofs that have been written during the 358 years between Fermat's statement and Wiles's proof.

History

The fundamental theorem can be derived from Book VII, propositions 30, 31 and 32, and Book IX, proposition 14 of Euclid's Elements. Template:Quotation

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

(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.<ref>Template:Harvtxt: "Even in Euclid, we fail to find a general statement about the uniqueness of the factorization of an integer into primes; surely he may have been aware of it, but all he has is a statement (Eucl.IX.I4) about the l.c.m. of any number of given primes."</ref> Indeed, in this proposition the exponents are all equal to one, so nothing is said for the general case.

While Euclid took the first step on the way to the existence of prime factorization, Kamāl al-Dīn al-Fārisī took the final step<ref>Template:Cite journal</ref> and stated for the first time the fundamental theorem of arithmetic.<ref>Template:Cite book</ref>

Article 16 of Gauss's Disquisitiones Arithmeticae is an early modern statement and proof employing modular arithmetic.<ref name="Gauss1801.loc=16" />

Applications

Canonical representation of a positive integer

Every positive integer Template:Math can be represented in exactly one way as a product of prime powers

<math>

n = p_1^{n_1}p_2^{n_2} \cdots p_k^{n_k} = \prod_{i=1}^{k} p_i^{n_i}, </math> where Template:Math are primes and the Template:Math 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 Template:Math).

This representation is called the canonical representation<ref>Template:Harvtxt</ref> of Template:Math, or the standard form<ref>Template:Harvtxt</ref><ref>Template:Harvtxt</ref> of n. For example,

999 = 3³×37,

1000 = 2³×5³,

1001 = 7×11×13.

Factors Template:Math may be inserted without changing the value of Template:Math (for example, Template:Math). In fact, any positive integer can be uniquely represented as an infinite product taken over all the positive prime numbers, as

<math>n=2^{n_1}3^{n_2}5^{n_3}7^{n_4}\cdots=\prod_{i=1}^\infty p_i^{n_i},</math>

where a finite number of the Template:Math 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:

<math>\begin{alignat}{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{alignat}</math>

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 (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 Template:Math is either prime or a product of primes. First, Template:Math is prime. Then, by strong induction, assume this is true for all numbers greater than Template:Math and less than Template:Math. If Template:Math is prime, there is nothing more to prove. Otherwise, there are integers Template:Math and Template:Math, where Template:Math, and Template:Math. By the induction hypothesis, Template:Math and Template:Math are products of primes. But then Template:Math is a product of primes.

Uniqueness

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

Uniqueness without Euclid's lemma

The fundamental theorem of arithmetic can also be proved without using Euclid's lemma.<ref>Template:Citation</ref> The proof that follows is inspired by Euclid's original version of the Euclidean algorithm.

Assume that <math>s</math> is the smallest positive integer which is the product of prime numbers in two different ways. Incidentally, this implies that <math>s</math>, if it exists, must be a composite number greater than <math>1</math>. Now, say

<math>

\begin{align} s &=p_1 p_2 \cdots p_m \\ &=q_1 q_2 \cdots q_n. \end{align} </math>

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

Setting <math>P=p_2\cdots p_m</math> and <math>Q=q_2\cdots q_n,</math> one has <math>s=p_1P=q_1Q.</math> Also, since <math>p_1 < q_1,</math> one has <math>Q < P.</math> It then follows that

<math>s-p_1Q = (q_1-p_1)Q = p_1(P-Q) < s.</math>

As the positive integers less than Template:Mvar have been supposed to have a unique prime factorization, <math>p_1</math> must occur in the factorization of either <math>q_1-p_1</math> or Template:Mvar. The latter case is impossible, as Template:Mvar, being smaller than Template:Mvar, must have a unique prime factorization, and <math>p_1</math> differs from every <math>q_j.</math> The former case is also impossible, as, if <math>p_1</math> is a divisor of <math>q_1-p_1,</math> it must be also a divisor of <math>q_1,</math> which is impossible as <math>p_1</math> and <math>q_1</math> 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 <math>1</math>, not factor into any prime.

Generalizations

Template:More citations needed section 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 <math>\mathbb{Z}[i].</math> 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 (except for order), the composites have unique factorization as a product of primes (up to the order and multiplication by units).<ref>Gauss, BQ, §§ 31–34</ref>

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

However, it was also discovered that unique factorization does not always hold. An example is given by <math>\mathbb{Z}[\sqrt{-5}]</math>. In this ring one has<ref>Template:Harvtxt</ref>

<math>

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

</math>

Examples like this caused the notion of "prime" to be modified. In <math>\mathbb{Z}\left[\sqrt{-5}\right]</math> 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 (1 + Template:Sqrt) nor (1 − Template:Sqrt) even though it divides their product 6. In algebraic number theory 2 is called irreducible in <math>\mathbb{Z}\left[\sqrt{-5}\right]</math> (only divisible by itself or a unit) but not prime in <math>\mathbb{Z}\left[\sqrt{-5}\right]</math> (if it divides a product it must divide one of the factors). The mention of <math>\mathbb{Z}\left[\sqrt{-5}\right]</math> is required because 2 is prime and irreducible in <math>\mathbb{Z}.</math> 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 <math>\mathbb{Z}</math> every irreducible is prime". This is also true in <math>\mathbb{Z}[i]</math> and <math>\mathbb{Z}[\omega],</math> but not in <math>\mathbb{Z}[\sqrt{-5}].</math>

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.

See also

• Integer factorization
• List of theorems called fundamental
• Prime signature, a characterization of how many primes divide a given number

References

Template:Sfn whitelist 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.

• Template:Citation
• Template:Citation

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".

• Template:Citation
• Template:Citation

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.

• Template:Citation
• Template:Hardy and Wright
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation

External links

• Why isn’t the fundamental theorem of arithmetic obvious?
• GCD and the Fundamental Theorem of Arithmetic at cut-the-knot.
• PlanetMath: Proof of fundamental theorem of arithmetic
• Fermat's Last Theorem Blog: Unique Factorization, a blog that covers the history of Fermat's Last Theorem from Diophantus of Alexandria to the proof by Andrew Wiles.
• "Fundamental Theorem of Arithmetic" by Hector Zenil, Wolfram Demonstrations Project, 2007.
• Template:CitationTemplate:Cbignore
• Fundamental Theorem of Arithmetic