Fundamental theorem of arithmetic

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Not to be confused with Fundamental theorem of algebra.

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 is either prime itself or is the product of prime numbers, and that, although the order of the primes in the second case is arbitrary, the primes themselves are not.^[1]^[2]^[3] For example,

$1200 = 2^4 \times 3^1 \times 5^2 = 3 \times 2\times 2\times 2\times 2 \times 5 \times 5 = 5 \times 2\times 3\times 2\times 5 \times 2 \times 2 =\cdots\text { etc.} \!$

The theorem is stating two things: first, that 1200 can be represented as a product of primes, and second, no matter how this is done, there will always be 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 (e.g. 12 = 2 × 6 = 3 × 4).

1 History
2 Applications
3 Proof
- 3.1 Existence
- 3.2 Uniqueness
4 Generalizations
5 See also
6 Notes
7 References
8 External links

History

Book VII, propositions 30 and 32 of Euclid's Elements is essentially the statement and proof of the fundamental theorem. 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:

$n = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k} = \prod_{i=1}^{k}p_i^{\alpha_i}$

where p₁ < p₂ < ... < p_k are primes and the α_i are positive integers.

This representation is called the canonical representation^[4] of n, or the standard form^[5]^[6] of n.

For example 999 = 3³×37, 1000 = 2³×5³, 1001 = 7×11×13

Note that factors p⁰ = 1 may be inserted without changing the value of n (e.g. 1000 = 2³×3⁰×5³).
In fact, any positive integer can be uniquely represented as an infinite product taken over all the positive prime numbers,

$n=2^{n_2}3^{n_3}5^{n_5}7^{n_7}\cdots=\prod p_i^{n_{p_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.

Arithmetic operations

This representation is convenient for expressions like these for the product, gcd, and lcm:

$a\cdot b =2^{a_2+b_2}\,3^{a_3+b_3}\,5^{a_5+b_5}\,7^{a_7+b_7}\cdots =\prod p_i^{a_{p_i}+b_{p_i}},$

$\gcd(a,b) =2^{\min(a_2,b_2)}\,3^{\min(a_3,b_3)}\,5^{\min(a_5,b_5)}\,7^{\min(a_7,b_7)}\cdots =\prod p_i^{\min(a_{p_i},b_{p_i})},$

$\operatorname{lcm}(a,b) =2^{\max(a_2,b_2)}\,3^{\max(a_3,b_3)}\,5^{\max(a_5,b_5)}\,7^{\max(a_7,b_7)}\cdots =\prod p_i^{\max(a_{p_i},b_{p_i})}.$

While expressions like these are of great theoretical importance their practical use is limited by our ability to factor numbers.

Arithmetical functions

Main article: Arithmetic function

Many arithmetical 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 p divides the product of two natural numbers a and b, then p divides a or p divides b (or both). The article has proofs of the lemma.

Existence

By induction: assume it is true for all numbers 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_n and b = q₁q₂...q_m are products of primes. But then n = ab = p₁p₂...p_nq₁q₂...q_m is the product of primes. In the base case, 2 is a trivial product of primes.

Uniqueness

Assume that s > 1 is the product of prime numbers in two different ways:

$\begin{align} s &=p_1 p_2 \cdots p_m \\ &=q_1 q_2 \cdots q_n. \end{align}$

We must show m = n and that the q_j are a rearrangement of the p_i.

By Euclid's lemma p₁ must divide one of the q_j; relabeling the q_j if necessary, say that p₁ divides q₁. But q₁ is prime, so its only divisors are itself and 1. Therefore, p₁ = q₁, so that

$\begin{align} \frac{s}{p_1} &=p_2 \cdots p_m \\ &=q_2 \cdots q_n. \end{align}$

Reasoning the same way, p₂ must equal one of the remaining q_j. Relabeling again if necessary, say p₂ = q₂. Then

$\begin{align} \frac{s}{p_1 p_2} &=p_3 \cdots p_m \\ &=q_3 \cdots q_n. \end{align}$

This can be done for all m of the p_i, showing that m ≤ n. If there were any q_j left over we would have

$\begin{align} \frac{s}{p_1 p_2 \cdots p_m} &=1 \\ &=q_k \cdots q_n, \end{align}$

which is impossible, since the product of numbers greater than 1 cannot equal 1. Therefore m = n and every q_j is a p_i.

Generalizations

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 $\mathbb{Z}[i].$ 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.^[7]

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

However, it was also discovered that unique factorization does not always hold. An example is given by $\mathbb{Z}[\sqrt{-5}]$ . In this ring one has^[8]

$6= 2\times 3= (1+\sqrt{-5})\times(1-\sqrt{-5}).$

Examples like this caused the notion of "prime" to be modified. In $\mathbb{Z}[\sqrt{-5}]$ 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 (1 + √−5) nor (1 − √−5) even though it divides their product 6. In algebraic number theory 2 is called irreducible (only divisible by itself or a unit) but not prime (if it divides a product it must divide one of the factors). Using these definitions it can be proven that in any ring a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers $\mathbb{Z}$ every irreducible is prime". This is also true in $\mathbb{Z}[i]$ and $\mathbb{Z}[\omega],$ but not in $\mathbb{Z}[\sqrt{-5}].$

The rings where every irreducible is prime are called unique factorization domains. As the name indicates, the fundamental theorem of arithmetic is true in them. Important examples are 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.

Notes

^ Long (1972, p. 44)
^ Pettofrezzo & Byrkit (1970, p. 53)
^ Hardy & Wright, Thm 2
^ Long (1972, p. 45)
^ Pettofrezzo & Byrkit (1970, p. 55)
^ Hardy & Wright § 1.2
^ Gauss, BQ, §§ 31–34
^ Hardy & Wright, § 14.6

References

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.

Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0387962549
Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8

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

Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima, Göttingen: Comment. Soc. regiae sci, Göttingen 6
Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda, Göttingen: Comment. Soc. regiae sci, Göttingen 7

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.

Baker, Alan (1984), A Concise Introduction to the Theory of Numbers, Cambridge, UK: Cambridge University Press, ISBN 978-0-521-28654-1
Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (fifth ed.), USA: Oxford University Press, ISBN 978-0-19-853171-5
A. Kornilowicz; P. Rudnicki (2004), "Fundamental theorem of arithmetic", Formalized Mathematics 12 (2): 179–185
Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950 .
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766 .
Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5
Weisstein, Eric W., "Abnormal number" from MathWorld.
Weisstein, Eric W., "Fundamental Theorem of Arithmetic" from MathWorld.

External links

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.
Grime, James. "1 and Prime Numbers". Numberphile. Brady Haran.

v t e Fundamental mathematical theorems

Arithmetic Algebra Calculus Geometry Curves Projective Riemannian Groups Cyclic Finitely generated Abelian Linear algebra Calculus of variations Vector analysis Homomorphisms Galois theory

v t e Divisibility-based sets of integers

Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic Arithmetic number

Factorization forms	Prime number Composite number Semiprime number Pronic number Sphenic number Square-free number Powerful number Perfect power Achilles number Smooth number Regular number Rough number Unusual number

Constrained divisor sums	Perfect number Almost perfect number Quasiperfect number Multiply perfect number Hemiperfect number Hyperperfect number Superperfect number Unitary perfect number Semiperfect number Practical number

With many divisors	Abundant number Primitive abundant number Highly abundant number Superabundant number Colossally abundant number Highly composite number Superior highly composite number Weird number

Aliquot sequence-related	Untouchable number Amicable number Sociable number Betrothed number

Other sets	Deficient number Friendly number Solitary number Sublime number Harmonic divisor number Frugal number Equidigital number Extravagant number