Fundamental theorem of arithmetic

From Wikipedia, the free encyclopedia

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

$6936 = 2^3 \times 3 \times 17^2 , \,\!$

$1200 = 2^4 \times 3 \times 5^2 . \,\!$

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 and associative, the order of factors is irrelevant and usually written from least to greatest.

Many authors take the natural numbers to begin with 0, which has no prime factorization. Thus Theorem 1 of Hardy & Wright (1979) takes the form, “Every positive integer, except 1, is a product of primes”, and Theorem 2 (their "Fundamental") asserts uniqueness. The number 1 is not itself prime, but since it is the product of no numbers, it is often convenient to include it in the theorem by the empty product rule. (See, for example, Calculating the gcd.)

Hardy & Wright define an abnormal number to be a hypothetical number that does not have a unique prime factorization. They prove the fundamental theorem of arithmetic by proving that there does not exist an abnormal number.

1 Applications
2 Proof
- 2.1 Euclid's proof
  - 2.1.1 Non-prime composite numbers
- 2.2 Proof by infinite descent
3 See also
4 References
5 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 a * 3 b * 17 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 $4 * 2 * 3 = 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 $23 * 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 practically proved by Euclid, but the first full and correct proof is found in the Disquisitiones Arithmeticae by Carl Friedrich Gauss. It may be important to note that Egyptians like Ahmes used earlier practical aspects of the factoring, and lowest common multiple, of the fundamental theorem of arithmetic allowing a long tradition to develop, as formalized by Euclid, and rigorously proven by 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 (see well-order): let it be n. This number n cannot be 1, because of the empty-product 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 proof by contradiction. This is a minimal counterexample argument.

[edit] Proof by infinite descent

A 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. Denote these two factorizations of $s\!$ as $p_1\ldots p_m\!$ and $q_1\ldots q_n\!$ , such that $s = p_1 p_2\ldots p_m = q_1 q_2\ldots q_n\!$ .

No $p_i\!$ (with $1 \le i \le m\!$ ) can be equal to any $q_j\!$ (with $1 \le j \le 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_1\!$ is a prime factor smaller than any $q_j\!$ (with $1 \le j \le n\!$ ). Let $d\!$ be the quotient and $r\!$ the remainder from dividing $q_1\!$ by $p_1\!$ . By the division algorithm $d\!$ and $r\!$ are guaranteed to be integers such that $q_1\ = dp_1 + r\!$ and $0 \le r < p_1\!$ . Note that $r\!$ can't be $0\!$ , as that would make $q_1\!$ a multiple of $p_1\!$ and not prime. Also $d \ge 1\!$ , since $q_1\!$ is greater than $p_1\!$ .

Substituting in for $q_1\!$ in the original definition of $s\!$ above,

$s = p_1 p_2\ldots p_m = (dp_1 + r) q_2\ldots q_n\!$

By distributivity:

$s = p_1 p_2\ldots p_m = d p_1 q_2\ldots q_n + r q_2\ldots q_n\!$

Define a new integer $k = s - d p_1 q_2\ldots q_n = r q_2\ldots q_n\!$ . Since $d \ge 1\!$ , it is clear that $k\!$ must be smaller than $s\!$ . And since $r > 0\!$ , $k\!$ must be positive. From the definition of $k\!$ , it follows that:

$k = p_1 p_2\ldots p_m - d p_1 q_2\ldots q_n\!$

and by factoring out $p_1\!$ :

$k = p_1 (p_2\ldots p_m - d q_2\ldots q_n)\!$

Therefore there is a prime factorization of $k\!$ that includes $p_1\!$ . But it is also true that

$k = r q_2\ldots q_n\!$

Since $r < p_1\!$ , $p_1\!$ cannot be a prime factor of $r\!$ . Thus, by combining the prime factors of $r\!$ with $q_2\ldots q_n\!$ , it is also possible to construct a prime factorization of $k\!$ that does not include $p_1\!$ . Therefore $k\!$ has two different prime factorizations, contradicting the original assumption that $s\!$ is the smallest integer factorizable in more than one way. Thus the original assumption must be false.