Fundamental theorem of arithmetic

From Wikipedia, the free encyclopedia

In number theory, the fundamental theorem of arithmetic (or unique factorization theorem) states that every natural number either is itself a prime number, or can be written as a unique product of prime numbers. For instance,

• 

• 

There are no other possible factorizations of 6936 or 1200 into prime numbers. The above representation collapses repeated prime factors into powers for easier identification. Because multiplication is commutative, the order of factors is irrelevant and usually written from smallest to largest.

While the value one is not itself prime, it is the product of no numbers by the empty product rule.

Contents 1 Applications 2 Proof 2.1 Euclid's Proof 2.1.1 Non-prime composite numbers 2.1.2 Unique Composition 2.2 Proof by infinite descent 2.3 Proof using abstract algebra 3 References 4 Bibliography 5 See also 6 External links

[edit] Applications

The fundamental theorem of arithmetic establishes the importance of prime numbers. Prime numbers are the basic building blocks of any positive integer, in the sense that each positive integer can be constructed from the product of primes with one unique construction. Finding the prime factorization of an integer allows derivation of all its divisors, both prime and non-prime.

For example, the above factorization of 6936 shows that any positive divisor of 6936 must have the form 2^a3^b17^c, where a takes one of the 4 values in {0, 1, 2, 3}, where b takes one of the 2 values in {0, 1}, and where c takes one of the 3 values in {0, 1, 2}. Multiplying the numbers of independent options together produces a total of 423 = 24 positive divisors.

Once the prime factorizations of two numbers are known, their greatest common divisor and least common multiple can be found quickly. For instance, from the above it is shown that the greatest common divisor of 6936 and 1200 is 2³ 3 = 24. However if the prime factorizations are not known, the use of the Euclidean algorithm generally requires much less calculation than factoring the two numbers.

The fundamental theorem ensures that additive and multiplicative arithmetic functions are completely determined by their values on the powers of prime numbers.

[edit] Proof

The theorem was essentially first proved by Euclid, but the first full and correct proof is found in the Disquisitiones Arithmeticae by Carl Friedrich Gauss.

Although at first sight the theorem seems 'obvious', it does not hold in more general number systems, including many rings of algebraic integers. This was first pointed out by Ernst Kummer in 1843, in his work on Fermat's last theorem. The recognition of this failure is one of the earliest developments in algebraic number theory.

[edit] Euclid's Proof

The proof consists of two steps. In the first step every number is shown to be a product of zero or more primes. In the second, the proof shows that any two representations may be unified into a single representation.

[edit] Non-prime composite numbers

Suppose there were a positive integer which cannot be written as a product of primes. Then there must be a smallest such number: let it be n. This number n cannot be 1, because of the convention above. It cannot be a prime number either, since any prime number is a product of a single prime, itself. So it must be a composite number. Thus

n = ab

where both a and b are positive integers smaller than n. Since n is the smallest number which cannot be written as a product of primes, both a and b can be written as products of primes. But then

n = ab

can be written as a product of primes as well, a contradiction. This is a minimal counterexample argument.

[edit] Unique Composition

The uniqueness part of the proof hinges on the following fact: if a prime number p divides a product ab, then it divides a or it divides b (Euclid's lemma). This is a lemma, to prove first. For that, if p doesn't divide a, then p and a are coprime and Bézout's identity yields integers x and y such that

px + ay = 1.

Multiplying with b yields

pbx + aby = b,

and since both summands on the left-hand side are divisible by p, the right-hand side is also divisible by p. That proves the lemma.

Given two products of primes which are equal, take any prime p from the first product. It divides the first product, and hence also the second. By the above fact, p must then divide at least one factor in the second product. But the factors are all primes themselves, so p must actually be equal to one of the factors of the second product. So p can be cancelled from both products. Continuing in this fashion, eventually the prime factors of the two products must match up precisely.

[edit] Proof by infinite descent

Another proof of the uniqueness of the prime factorization of a given integer uses infinite descent: Assume that a certain integer can be written as (at least) two different products of prime numbers, then there must exist a smallest integer s with such a property. Call the two products of s p₁ ... p_m and q₁ ... q_n. No p_i (with 1 ≤ i ≤ m) can be equal to any q_j (with 1 ≤ j ≤ n), as there would otherwise be a smaller integer factorizable in two ways (by removing prime factors common in both products) violating the above assumption. Now it can be assumed without loss of generality that p₁ is a prime factor smaller than any q_j (with 1 ≤ j ≤ n). Take q₁. Then there exist integers d and r such that

q₁/p₁ = d + r/p₁

and 0 < r < p₁ < q₁ (r can't be 0, as that would make q₁ a multiple of p₁ and not prime). Multiplying both sides by s / q₁, the result is

p₂ ... p_m = (d + r/p₁) q₂ ... q_n = dq₂ ... q_n + rq₂ ... q_n/p₁.

The second term in the last expression must be equal to an integer, which can be called k, i.e.

k = rq₂ ... q_n/p₁.

This gives

p₁k = rq₂ ... q_n.

The value of both sides of this equation is obviously smaller than s, but is still large enough to be factorizable. Since r is smaller than p₁, the two prime factorizations we get on each side after both k and r are written out as their product of primes must be different. This is in contradiction with s being the smallest integer factorizable in more than one way. Thus the original assumption must be false.

[edit] Proof using abstract algebra

Let n be an integer. Z_n is a finite group and therefore has a composition series. By definition, the factors in a composition series are simple. Hence the factors in a composition series of Z_n are of the form Z_p for some prime number p. Since the order of Z_n is the product of the orders of the factors of the composition series, this gives a factorization of n into prime numbers. But the Jordan-Hölder theorem says that our composition series is unique, and hence the prime factorization of n must be unique.

[edit] References

[edit] Bibliography

• Baker, Alan, A Concise Introduction to the Theory of Numbers, Cambridge University Press, Cambridge, UK, 1984). ISBN 0-521-28654-9.

[edit] See also

• Fundamental theorem of algebra
• Fundamental theorem of calculus
• Integer factorization
• Prime factorization algorithm
• Prime signature
• Maris-McGwire-Sosa pairs

[edit] 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.