- Fundamental theorem of arithmetic
In

number theory , the**fundamental theorem of arithmetic**(or**unique-prime-factorization theorem**) states that everynatural number greater than 1 can be written as a unique product ofprime number s. For instance,: $6936\; =\; 2^3\; imes\; 3\; imes\; 17^2\; ,\; ,!$

: $1200\; =\; 2^4\; imes\; 3\; imes\; 5^2\; .\; ,!$

There are no other possible

factorization s of 6936 or 1200 into non-negative prime numbers. The above representation collapses repeated prime factors into powers for easier identification. Because multiplication iscommutative andassociative , 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 Harvtxt|Hardy|Wright|1979 takes the form, “Every positive integer, except 1, is a product of 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.)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.**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 andleast 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}× 3 = 24. However, if the prime factorizations are not known, the use of theEuclidean algorithm generally requires much less calculation than factoring the two numbers.The fundamental theorem ensures that additive and multiplicative

arithmetic function s are completely determined by their values on the powers of prime numbers.**Proof**The theorem was practically proved by

Euclid , but the first full and correct proof is found in theDisquisitiones Arithmeticae byCarl Friedrich Gauss . It may be important to note that Egyptians likeAhmes used earlier practical aspects of the factoring, andlowest 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 byErnst Kummer in 1843, in his work onFermat's Last Theorem . The recognition of this failure is one of the earliest developments inalgebraic number theory .**Euclid's proof (of existence)**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 (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.**Proof by infinite descent (of uniqueness)**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}···"p"_{"m"}and "q"_{ 1}···"q"_{"n"}, such that "s" = "p"_{1}"p"_{2}···"p"_{"m"}= "q"_{ 1}"q"_{2}···"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 assumedwithout loss of generality that "p"_{1}is a prime factor smaller than any "q"_{ "j"}(with 1 ≤ "j" ≤ "n"). Let "d" be thequotient and "r" theremainder from dividing "q"_{ 1}by "p"_{1}. By thedivision algorithm "d" and "r" are guaranteed to be integers such that "q"_{ 1}= "dp"_{1}+ "r" and 0 ≤ "r" < "p"_{1}. Note immediately that since "q"_{ 1}is prime it cannot be a multiple of "p"_{1}and thus:$r\; eq\; 0.!$

Also, since "q"

_{1}is greater than "p"_{1}:$d\; ge\; 1.!$

Substituting in for "q"

_{1}in the original definition of "s" above,: $s\; =\; p\_1\; p\_2cdots\; p\_m\; =\; (dp\_1\; +\; r)\; q\_2cdots\; q\_n.!$

By

distributivity :: $s\; =\; p\_1\; p\_2cdots\; p\_m\; =\; d\; p\_1\; q\_2cdots\; q\_n\; +\; r\; q\_2cdots\; q\_n.!$

Define a new integer "k" = "s" −"dp"

_{1}"q"_{2}···"q"_{"n"}= "rq"_{2}···"q"_{"n"}. Since "d"≥ 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\_2cdots\; p\_m\; -\; d\; p\_1\; q\_2cdots\; q\_n!$

and by factoring out "p"

_{1}:: $k\; =\; p\_1\; (p\_2cdots\; p\_m\; -\; d\; q\_2cdots\; q\_n).!$

Therefore there is a prime factorization of "k" that includes "p"

_{1}. But it is also true that: $k\; =\; r\; q\_2cdots\; 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}···"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.**ee also***

Fundamental theorem of algebra

*Fundamental theorem of calculus

*Integer factorization

*Prime signature

*Unique factorization domain **References*** Citation

last1=Hardy

first1=G. H.

author1-link=G. H. Hardy

last2=Wright

first2=E. M.

author2-link=E. M. Wright

year=1979

title=An Introduction to the Theory of Numbers

edition=fifth

place=USA

publisher=Oxford University Press

isbn=978-0-19-853171-5

* Citation

last=Baker

first=Alan

author-link=

year=1984

title=A Concise Introduction to the Theory of Numbers

place=Cambridge, UK

publisher=Cambridge University Press

isbn=978-0-521-28654-1

*

***External links*** [

*http://www.cut-the-knot.org/blue/gcd_fta.shtml GCD and the Fundamental Theorem of Arithmetic*] atcut-the-knot

* [*http://planetmath.org/encyclopedia/ProofOfFundamentalTheoremOfArithmetic.html PlanetMath: Proof of fundamental theorem of arithmetic*]

* [*http://fermatslasttheorem.blogspot.com/2005/06/unique-factorization.html 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.

* [*http://demonstrations.wolfram.com/FundamentalTheoremOfArithmetic/ "Fundamental Theorem of Arithmetic"*] by Hector Zenil,The Wolfram Demonstrations Project , 2007.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**fundamental theorem of arithmetic**— Fundamental principle of number theory proved by Carl Friedrich Gauss in 1801. It states that any integer greater than 1 can be expressed as the product of prime numbers in only one way. * * * Fundamental principle of number theory proved… … Universalium**Fundamental theorem**— In mathematics, there are a number of fundamental theorems for different fields. The names are mostly traditional; so that for example the fundamental theorem of arithmetic is basic to what would now be called number theory. Theorems may be… … Wikipedia**Fundamental**— may refer to: * Fundamental frequency,a concept in music or phonetics, often referred to as simply a fundamental . * Fundamentalism, the belief in, and usually the strict adherence to, the simplistic or fundamental ideas based on faith of a… … Wikipedia**Arithmetic**— tables for children, Lausanne, 1835 Arithmetic or arithmetics (from the Greek word ἀριθμός, arithmos “number”) is the oldest and most elementary branch of mathematics, used b … Wikipedia**arithmetic**— arithmetically, adv. n. /euh rith meuh tik/; adj. /ar ith met ik/, n. 1. the method or process of computation with figures: the most elementary branch of mathematics. 2. Also called higher arithmetic, theoretical arithmetic. the theory of… … Universalium**Arithmetic function**— In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers (i.e. positive integers) that expresses some arithmetical property of n. [1] An example of an arithmetic… … Wikipedia**theorem**— theorematic /thee euhr euh mat ik, thear euh /, adj. theorematically, adv. /thee euhr euhm, thear euhm/, n. 1. Math. a theoretical proposition, statement, or formula embodying something to be proved from other propositions or formulas. 2. a rule… … Universalium**fundamental**— fundamentality, fundamentalness, n. fundamentally, adv. /fun deuh men tl/, adj. 1. serving as, or being an essential part of, a foundation or basis; basic; underlying: fundamental principles; the fundamental structure. 2. of, pertaining to, or… … Universalium**Theorem**— The Pythagorean theorem has at least 370 known proofs[1] In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements … Wikipedia**Euclid's theorem**— is a fundamental statement in number theory which asserts that there are infinitely many prime numbers. There are several well known proofs of the theorem.Euclid s proofEuclid offered the following proof published in his work Elements (Book IX,… … Wikipedia