fundamental theorem of arithmetic, proof of the

To prove the fundamental theorem of arithmeticMathworldPlanetmath, 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 domainMathworldPlanetmath, every prime is an irreducible elementMathworldPlanetmath. Furthermore, by Euclid’s lemma, every irreducible element in is prime. As a result, prime elementsMathworldPlanetmath and irreducible elements are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath in . We will use this fact to prove the theorem.

Note: all our arithmetic will be carried out in the natural numbersMathworldPlanetmath, not the integers.


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 numberMathworldPlanetmath has a prime decomposition. We claim that any composite number is divisible by some prime numberMathworldPlanetmath. 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 productPlanetmathPlanetmath of smaller positive integers in the same way. Continuing this process, we obtain a strictly decreasing sequenceMathworldPlanetmath of natural numbers. By the well-ordering 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 completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof of existence, we apply the well-ordering 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 well-ordering 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.


Now we show uniqueness up to order of factors. Suppose we are given two prime decompositions


of n, where k and the factors in each prime decomposition are arranged in nondecreasing order. Since p1 divides n, it divides the product q1q, so by primality must divide some qi. Thus there is a natural number b such that qi=bp1. Since qi is an irreducible element and p1 is not a unit, it must be that b is a unit, that is, b = 1. Hence p1=qiq1. Similarly, there is some j such that q1=pjp1. Since p1q1 and q1p1, it follows that p1=q1. Cancelling these factors yields the simpler equation


By repeating the above procedure we can show that pi=qi for all i from 0 to k. Cancelling these factors gives the equation


Since a nontrivial product of primes is greater than 1, the right-hand 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 inductionMathworldPlanetmath: 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.

Title fundamental theorem of arithmetic, proof of the
Canonical name FundamentalTheoremOfArithmeticProofOfThe
Date of creation 2013-03-22 11:48:00
Last modified on 2013-03-22 11:48:00
Owner mps (409)
Last modified by mps (409)
Numerical id 16
Author mps (409)
Entry type Proof
Classification msc 11-00
Classification msc 16U99
Classification msc 13A99