Fundamental theorem of arithmetic

related topics
{math, number, function}
{village, small, smallsup}
{god, call, give}

In number theory, the Fundamental Theorem of Arithmetic (or Unique-Prime-Factorization 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 non-zero 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 non-prime.

Full article ▸

related documents
Pell's equation
Delaunay triangulation
Selection sort
Naive Bayes classifier
Binomial theorem
Tensor
Brouwer fixed point theorem
Affine transformation
Greatest common divisor
Polish notation
Befunge
Knapsack problem
Empty set
NP (complexity)
Net (mathematics)
Direct product
Shell sort
Scientific notation
Grover's algorithm
Tree automaton
Curve
Root-finding algorithm
Finite state machine
Brute force attack
Cyclic group
Symmetric matrix
Graph theory
Ordered pair
Partially ordered set
Analytic function