Fundamental theorem of arithmetic
From Academic Kids

In mathematics, and in particular number theory, the fundamental theorem of arithmetic or unique factorization theorem is the statement that every positive integer greater than 1 can be written as a product of prime numbers in only one way. For instance, we can write
 6936 = 2^{3} · 3 · 17^{2} or 1200 = 2^{4} · 3 · 5^{2}
and there are no other possible factorizations of 6936 or 1200 into prime numbers, if we ignore the ordering of the factors.
To make the theorem work even for the number 1, we can think of 1 as being the product of zero prime numbers (see empty product).
Contents 
Applications
The theorem establishes the importance of prime numbers. The prime numbers are the basic building blocks of the positive integers, in the sense that every positive integer can be constructed from primes, and there is essentially only one such construction.
Knowing the prime number factorization of a number gives complete knowledge about all factors of that number. For instance, the above factorization of 6936 tells us that the positive factors of 6936 are of the form
 2^{a} · 3^{b} · 17^{c}
with [0 ≤ a ≤ 3], [0 ≤ b ≤ 1], and [0 ≤ c ≤ 2]. This yields a total of 4 · 2 · 3 = 24 positive factors.
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 we see that the greatest common divisor of 6936 and 1200 is 2^{3} · 3 = 24. However if the prime factorizations are not known, the use of Euclid's 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.
Proof
The theorem was essentially first proved by Euclid. Although at first sight it 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.
The proof consists of two parts: first, we have to show that every number can indeed be written as a product of primes; then we have to show that any two such representations are essentially the same.
Suppose there was a positive integer which can not be written as a product of primes. Then there must be a smallest such number: let's call it n. This number n cannot be 1, because of our 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 was the smallest number for which the theorem fails, 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.)
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 lefthand side are divisible by p, the righthand side is also divisible by p. That proves the lemma.
Now take 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 we can cancel p from both products. Continuing in this fashion, we eventually see that the prime factors of the two products must match up precisely.
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_{1} ... p_{m} and q_{1} ... 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 our assumption. We can now assume without loss of generality that p_{1} is a prime factor smaller than any q_{j} (with 1 ≤ j ≤ n). Take q_{1}. Then there exist integers d and r such that
 q_{1}/p_{1} = d + r/p_{1}
and 0 < r < p_{1} < q_{1} (r can't be 0, as that would make q_{1} a multiple of p_{1} and not prime). We now get
 p_{2} ... p_{m} = (d + r/p_{1}) q_{2} ... q_{n} = dq_{2} ... q_{n} + rq_{2} ... q_{n}/p_{1}.
The second term in the last expression must be equal to an integer we call k, i.e.
 k = rq_{2} ... q_{n}/p_{1}.
This gives us
 p_{1}k = rq_{2} ... 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_{1}, 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.
See also
References
 Baker, Alan (1984). A Concise Introduction to the Theory of Numbers. Cambridge: Cambridge University Press. ISBN 0521286549
External links
 GCD and the Fundamental Theorem of Arithmetic (http://www.cuttheknot.org/blue/gcd_fta.shtml)
 PlanetMath: Proof of fundamental theorem of arithmetic (http://planetmath.org/encyclopedia/ProofOfFundamentalTheoremOfArithmetic.html)
 Fermat's Last Theorem Blog: Unique Factorization (http://fermatslasttheorem.blogspot.com/2005/06/uniquefactorization.html), A blog that covers the history of Fermat's Last Theorem from Diophantus of Alexandria to the proof by Andrew Wiles.de:Fundamentalsatz der Arithmetik
es:Teorema fundamental de la Aritmética fr:Théorème fondamental de l'arithmétique it:Teorema fondamentale dell'aritmetica he:המשפט היסודי של האריתמטיקה hu:A számelmélet alaptétele nl:Hoofdstelling van de rekenkunde pl:Podstawowe twierdzenie arytmetyki ru:Основная теорема арифметики th:ทฤษฎีบทมูลฐานของเลขคณิต tr:Aritmetiğin Temel Teoremi zh:算术基本定理