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, Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...

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. In mathematics, factorization or factoring is the decomposition of an object (for example, a number, a polynomial, or a matrix) into a product of other objects, or factors, which when multiplied together give the original. ... Mathematical meaning A map or binary operation is said to be commutative when, for any x in A and any y in B . ...

While the value 1 is not itself prime, it is the product of no numbers by the empty product rule. In mathematics, an empty product, or nullary product, is the result of multiplying no numbers. ...

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. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ... In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ... In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ...

The fundamental theorem ensures that additive and multiplicative arithmetic functions are completely determined by their values on the powers of prime numbers. In number theory, an additive function is an arithmetic function f(n) of the positive integer n such that whenever a and b are coprime we have: f(ab) = f(a) + f(b). ... In number theory, a multiplicative function is an arithmetic function f(n) of the positive integer n with the property that f(1) = 1 and whenever a and b are coprime, then f(ab) = f(a) f(b). ... In number theory, an arithmetic function (or number-theoretic function) f(n) is a function defined for all positive integers and having values in the complex numbers. ...

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. Euclid, is also referred to as Euclid of Alexandria, (Greek: , 330 BC – 275 BC), a Greek mathematician, who lived in the city of Alexandria, Egypt, almost certainly during the reign of Ptolemy I (323–283 BC), is often considered to be the father of geometry. His most popular work, Elements... The Disquisitiones Arithmeticae is a textbook of number theory written by German mathematician Carl Friedrich Gauss and first published in 1801 when Gauss was 24. ...   (23 April 1776 – 29 February 1855) was a German mathematician and scientist of profound genius who contributed significantly to many fields, including integral number theory, analysis, differential geometry, geodesy, magnetism, astronomy and optics. ...

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. In mathematics, an algebraic integer is a complex number α that is a root of an equation P(x) = 0 where P(x) is a monic polynomial (that is, the coefficient of the largest power of x in P(x) is one) with integer coefficients. ... Ernst Eduard Kummer (29 January 1810 in Sorau, Brandenburg, Prussia - 14 May 1893 in Berlin, Germany) was a German mathematician. ... Pierre de Fermat Problem II.8 in the Arithmetica of Diophantus, annotated with Fermats comment which became Fermats Last Theorem (edition of 1670). ... This article or section does not cite its references or sources. ...

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.

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 In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ...

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. Broadly speaking, a contradiction is an incompatibility between two or more statements, ideas, or actions. ... In mathematics, the method of considering a minimal counterexample combines the ideas of inductive proof and proof by contradiction. ...

Unique decomposition

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 Euclids lemma is a generalisation of Proposition 30 of Book VII of Euclids Elements. ... In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than an independent statement, in and of itself. ... Coprime - Wikipedia /**/ @import /skins-1. ... In number theory, Bézouts identity, named after Étienne Bézout, is a linear diophantine equation. ...

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.

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 In mathematics, a proof by infinite descent is a particular kind of proof by mathematical induction. ... Without loss of generality or simply WLOG is a frequently used expression in mathematics. ...

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. The word term refers to either a word unit or a time unit with specified boundaries or limits. ... An expression in the very basic sense is the noun form of the verb express. ...

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. Broadly speaking, a contradiction is an incompatibility between two or more statements, ideas, or actions. ...

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. In mathematics, a composition series of a group G is a chain of subgroups of G satisfying where stands for normal subgroup, such that each quotient group Hi+1/Hi is a simple group. ... In mathematics, a composition series of a group G is a normal series such that each Hi is a maximal normal subgroup of Hi+1. ...

See also

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

In mathematics, the fundamental theorem of algebra states that every complex polynomial in one variable and of degree  â‰¥  has some complex root. ... The fundamental theorem of calculus is the statement that the two central operations of calculus, differentiation and integration, are inverse functions of one another. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... A prime factorization algorithm is any algorithm by which an integer (whole number) is decomposed into a product of factors that are prime numbers (Prime factor). ... The prime signature of a number is the sequence of exponents of its prime factorisation sorted in order of size. ... Maris-McGwire-Sosa pairs or MMS pairs are two numbers that when you add the digits of the numbers and the digits of its prime factorization, they are equal. ...

References

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

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.