Theorem. (Fundamental Theorem of Arithmetic) Every integer greater than 1 can be written in the form
In this product, and the
's are distinct primes. The factorization is unique,
except possibly for the order of the factors.
For instance,
I need a couple of lemmas in order to prove the uniqueness part of the Fundamental Theorem. In fact, these lemmas are useful in their own right.
Theorem. If and
, then
.
Proof. Write
Then
Now and
(since
), so
.
Theorem. If p is prime and , then
for some i.
For , the result says that if p is prime and
, then
or
. This is often called Euclid's
lemma.
Proof. The result is trivial if , since it says that if
, then
.
Do the case first. Suppose
, and suppose
. I must show
.
, and p is prime, so
or
. If
, then
,
which contradicts
. Therefore,
. By the preceding theorem,
. This establishes the result for
.
Assume , and assume the result is true when p
divides a product of with less than n factors. Suppose that
. Grouping the terms, I have
By the case , either
or
. If
, I'm done. Otherwise,
if
, then p divides one of
,
, ...,
, by induction. In either case, I've shown that p
divides one of the
's, which completes the induction
step and the proof.
Using these results, I'll prove the Fundamental Theorem of Arithmetic.
Proof. ( Fundamental Theorem of Arithmetic) First, I'll use induction to show that every integer greater than 1 can be expressed as a product of primes.
is prime, so the result is true for
.
Suppose , and assume every number less than n can
be factored into a product of primes. If n is prime, I'm done.
Otherwise, n is composite, so I can factor n as
, where
. By induction, a and
b can be factored into primes. Then
shows that n can, too.
Now I'll prove the uniqueness part of the Fundamental Theorem.
Suppose that
Here the p's are distinct primes, the q's are distinct primes, and
all the exponents are greater than or equal to 1. I want to show that
, and that each
is
for some b --- that is,
and
.
Consider . It divides the left side, so it divides
the right side. By the last lemma,
for some i. But
is
(
times), so again by the last lemma,
. Since
and
are prime,
.
To avoid a mess, renumber the q's so becomes
and vice versa. Thus,
, and the equation reads
If , cancel
from both sides, leaving
This is impossible, since now divides the left side,
but not the right.
For the same reason is impossible.
It follows that . So I can cancel the
's off both sides, leaving
Keep going. At each stage, I pair up a power of a p with a power of a
q, and the preceding argument shows the powers are equal. I can't
wind up with any primes left over at the end, or else I'd have a
product of primes equal to 1. So everything must have paired up, and
the original factorizations were the same (except possibly for the
order of the factors).
Recall that the least common multiple of
nonzero integers a and b is the smallest positive integer divisible
by both a and b. The least common multiple of a and b is denoted .
For example,
Here's an interesting fact that is easy to derive from the Fundamental Theorem.
Proposition. If a and b are nonzero integers,
then .
Proof. (sketch) Factor a and b in products of
primes, but write out all the powers (e.g. write as
):
Here the q's are the primes a and b have in common, and the p's and r don't overlap. Picture:
From the picture,
Thus, .
You might see if you can prove this proposition without using the Fundamental Theorem (that is, without factoring a and b into products of primes.
Here's how this result looks for 36 and 90:
We have and
; notice that
.
Copyright 2019 by Bruce Ikenaga