Fundamental Theorem of Arithmetic - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

Before diving into the Fundamental Theorem of Arithmetic, we need to first dispatch with an old claim. Namely, that if p is prime and p | ab,  either p | a or p | b.

Proof: Consider what values gcd(a,p) can have. Since p is prime, either gcd(a,p) =1 orgcd(a,p) = p. In the latter case, p | a and we are done. So, let us focus on the case where p and a are relatively prime. When gcd(a,p)=1, we know that we can find integers x and y that satisfy

px+ay=1

Now, multiply both sides of the equation by b to give

pbx+aby=b

Certainly, p | pbx. We also know that p | aby (since we know p | ab). It follows that p divides the sum of these two terms.

p | pbx+aby

But this sum is b, so p ∣ b, which completes the proof.

We can generalize the above claim in the following way:

The Prime Divisibility Property Let p be a prime number, and suppose that p|a₁a₂⋯a_r. Then p divides at least one of the factors a₁,a₂,...a_r.

Proof: If p | a₁ we are done. If not, we apply the claim argued above to the product

a₁(a₂a₃⋯ar)

to conclude that p | a₂a₃⋯a_r.. In other words, we are applying the claim with a=a₁ and b=a₂a₃⋯a_r. We know that p | ab, so if p | a, the claim requires that p | b. So now we know that p |a₂a₃⋯a_r. If p | a₂ we are done. If not, we apply the claim to the product a₂(a₃⋯a_r) to conclude that p | a₃⋯a_r. Continuing in this fashion, we must eventually find some a_i that is divisible by p.

Now, we have the machinery we need to tackle...

The Fundamental Theorem of Arithmetic Every integer n≥2 can be factored into a product of primes in exactly one way (aside from rearranging the factors).

Proof: We can prove the first part of this theorem (that every integer n≥2 can be factored into a product of primes) with strong induction. We'll save proving the uniqueness of the factorization for later...

Basis Step: Observe that 2=2, 3=3, 4=2⋅2, and so on... Clearly, the first several numbers can be factored into a product of primes.

Inductive Step: Suppose that we know every number n≤k can be factored into a product of primes. Let us consider n=k+1.

There are two possibilities. Either k+1 is prime (in which case we are done) or k+1 is composite. Recall that a number greater than 2 is composite (i.e., not prime) if and only if it has factors other than itself or 1. Consequently, we can find integers n₁n₁ and n₂n₂ where

k+1=n₁n₂ where 2≤n₁,n₂≤k

But both n₁ and n₂, being less than or equal to kk and greater than or equal to 2 have prime factorizations by the inductive hypothesis! Suppose these prime factorizations are

n₁= p₁p₂⋯p_r and n₂ = q₁q₂⋯q_s

But then, multiplying these two products together gives

k+1=n₁n₂=p₁p₂⋯p_rq₁q₂⋯q_s

So k+1 can be factored into a product of primes, which is what we sought to show.

With the principle of strong mathematical induction, we can then conclude that every integer n≥2 can be factored into a product of primes.

Now, to prove the uniqueness of this factorization, we appeal to an indirect argument. Suppose the factorization is not unique - that instead,

n=p₁p₂p₃p₄⋯pr=q₁q₂q₃q₄⋯qs

where the factorization on the right is not just a rearrangement of the factorization on the left. Note p₁ | n, so by the Prime Divisibility Property, p₁ must divide some q_i. Without loss of generality, suppose that i=1 (note, we can rearrange the q's if necessary). But we have p₁ | q₁ where q₁ is prime. Prime numbers are only divisible by themselves and 1, and seeing as how p₁≠1 since it too is prime, it must be the case that p₁=q₁.

So we may cancel the p₁ (which is the same as q₁) from both sides to arrive at

p₂p₃p₄⋯p_r=q₂q₃q₄⋯q_s

Repeating the same argument, we note that p₂ divides the left side, so p₂ divides the right side as well. Again, by the Prime Divisibility Property, p₂ divides some q_j, which we may call q₂ (after rearranging the factors, if needed). Thus p₂ | q₂, and given that they are both prime, we have p₂ = q₂. Canceling the p₂ (which equals q₂) from both sides, we have

p₃p₄⋯pr=q₃q₄⋯q_s

We continue in this fashion until either all of the p_i's or all of the q_i's are gone. But if all of the pipi's are gone, then the left side of the equation equals 1, and so the q_i's must have been exhausted as well. This argument works just as easily if all of the q_i's disappeared first. Being able to match up each p_i with some equal q_i implies that the q_i's are just a rearrangement of the p_i's, which contradicts our assumption. Hence, the prime factorization for any n≥2 is unique.