In number theory, the Fundamental Theorem of Arithmetic (or UniquePrimeFactorization Theorem) states that any integer greater than 1 can be written as a unique product (up to ordering of the factors) of prime numbers. For example,
are two examples of numbers satisfying the hypothesis of the theorem that can be written as the product of prime numbers. Intuitively, this theorem characterizes prime numbers uniquely in the sense that they are the "fundamental numbers."
Proof of existence of a prime factorization is straightforward: proof of uniqueness is more challenging. Some proofs use the fact that if a prime number p divides the product of two natural numbers a and b, then p divides either a or b, a statement known as Euclid's lemma. Since multiplication on the integers is both commutative and associative, it does not matter in what way we write a number greater than 1 as the product of primes; it is generally common to write the (prime) factors in the order of smallest to largest.
Some natural extensions of the hypothesis of this theorem allow any nonzero integer to be expressed as the product of "prime numbers" and "invertibles". For example, 1 and 1 are allowed to be factors of such representations (although they are not considered to be prime). In this way, one can extend the Fundamental Theorem of Arithmetic to any Euclidean domain or principal ideal domain bearing in mind certain alterations to the hypothesis of the theorem. A ring in which the Fundamental Theorem of Arithmetic holds is called a unique factorization domain.
Many authors assume 1 to be a natural number that has no prime factorization. Thus Theorem 1 of Hardy & Wright (1979) takes the form, "Every positive integer, except 1, is a product of one or more primes," and Theorem 2 (their "Fundamental") asserts uniqueness. By convention, 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.)
Contents
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 nonprime.
Full article ▸
