You are here
Homefundamental theorem of arithmetic, proof of the
Primary tabs
fundamental theorem of arithmetic, proof of the
To prove the fundamental theorem of arithmetic, we must show that each positive integer has a prime decomposition and that each such decomposition is unique up to the order of the factors. Before proceeding with the proof, we note that in any integral domain, every prime is an irreducible element. Furthermore, by Euclid’s lemma, every irreducible element in $\mathbb{Z}$ is prime. As a result, prime elements and irreducible elements are equivalent in $\mathbb{Z}$. We will use this fact to prove the theorem.
Note: all our arithmetic will be carried out in the natural numbers, not the integers.
 Existence

Now we prove the existence of a prime decomposition. Since 1 has a prime decomposition and any prime has a prime decomposition, it suffices to show that any composite number has a prime decomposition. We claim that any composite number is divisible by some prime number. To see this, assume n is a composite positive integer. Then there exist positive integers a and b, necessarily strictly smaller than n, such that n = ab. If a is not prime we can write it as a product of smaller positive integers in the same way. Continuing this process, we obtain a strictly decreasing sequence of natural numbers. By the wellordering principle, this sequence must terminate, and by construction, it must terminate in a prime number. Hence n is divisible by a prime number, as desired.
To complete the proof of existence, we apply the wellordering principle again. If n is composite, then it is divisible by some prime. Moreover, the quotient is strictly smaller than n. If the quotient is not prime then as before we find a prime that divides it; continuing this process, we produce a strictly decreasing sequence of natural numbers. By the wellordering principle, this sequence terminates in a prime number. The product of the prime numbers we found in the construction of this sequence is simply n. Thus every composite number has a prime decomposition.
 Uniqueness

Now we show uniqueness up to order of factors. Suppose we are given two prime decompositions
$n=p_{1}\cdots p_{k}=q_{1}\cdots q_{{\ell}}$ of n, where $k\leq\ell$ and the factors in each prime decomposition are arranged in nondecreasing order. Since $p_{1}$ divides n, it divides the product $q_{1}\cdots q_{{\ell}}$, so by primality must divide some $q_{i}$. Thus there is a natural number b such that $q_{i}=b\cdot p_{1}$. Since $q_{i}$ is an irreducible element and $p_{1}$ is not a unit, it must be that b is a unit, that is, b = 1. Hence $p_{1}=q_{i}\geq q_{1}$. Similarly, there is some j such that $q_{1}=p_{j}\geq p_{1}$. Since $p_{1}\geq q_{1}$ and $q_{1}\geq p_{1}$, it follows that $p_{1}=q_{1}$. Cancelling these factors yields the simpler equation
$p_{2}\cdots p_{k}=q_{2}\cdots q_{{\ell}}.$ By repeating the above procedure we can show that $p_{i}=q_{i}$ for all i from 0 to k. Cancelling these factors gives the equation
$1=q_{{k+1}}\cdots q_{{\ell}}.$ Since a nontrivial product of primes is greater than 1, the righthand side of this equation is the empty product. We conclude that k = l. Hence all prime decompositions of n use the same number of factors, and the factors which appear are unique up to the order in which they appear. This completes the proof of uniqueness and thereby the proof of the theorem.
Remark. Note that Euclid’s Lemma is necessary in order to prove the uniqueness portion of the theorem. Also, an alternative way of proving the existence portion of the theorem is to use induction: if $n$ is composite, then $n=ab$ for some integers $a,b<n$ (this is true, for if one of $a,b$ is $n$, then the other integer must be $1$). By induction, both $a$ and $b$ can be written as product of primes, which implies that $n$ is a product of primes.
Mathematics Subject Classification
1100 no label found16U99 no label found13A99 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new question: Prove a formula is part of the Gentzen System by LadyAnne
Mar 30
new question: A problem about Euler's totient function by mbhatia
new problem: Problem: Show that phi(a^n1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia
new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz
Mar 26
new correction: Misspelled name by DavidSteinsaltz
Mar 21
new correction: underlinetypo by Filipe
Mar 19
new correction: cocycle pro cocyle by pahio
Mar 7
new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier
new image: expected waiting time by robert_dodier
new image: plot W(t) = P(waiting time <= t) by robert_dodier