3Division
IA Numbers and Sets
3.2 Primes
There are a lot of ways we can define prime numbers in
N
. The definition we
will use is the following:
Definition
(Prime number)
. p ∈ N
is a prime if
p >
1 and the only factors of
p
(in Z) are ±1 and ±p.
In this chapter, the objective is to prove things we already know and think
are obvious.
Theorem. Every number can be written as a product of primes.
Proof.
If
n ∈ N
is not a prime itself, then by definition
n
=
ab
. If either
a
or
b
is not prime, then that number can be written as a product, say
b
=
cd
. Then
n
=
acd
and so on. Since these numbers are getting smaller, and the process
will stop when they are all prime.
In the proof, we handwaved a bit when we said “and so on”. We will later
come up with the principle of (strong) induction that rigorously justifies this.
This is the case for many proofs we will have here.
Theorem. There are infinitely many primes.
Proof.
(Euclid’s proof) Suppose there are finitely many primes, say
p
1
, p
2
···p
n
.
Then
N
=
p
1
p
2
···p
n
+ 1 is divisible by none of the primes. Otherwise,
p
j
|
(
N − p
1
p
2
···p
n
), i.e.
p
j
|
1, which is impossible. However,
N
is a product of
primes, so there must be primes not amongst p
1
, p
2
···p
n
.
Proof.
(Erd¨os 1930) Suppose that there are finitely many primes,
p
1
, p
2
···p
k
.
Consider all numbers that are the products of these primes, i.e.
p
j
1
1
p
j
2
2
···p
j
k
k
,
where
j
i
≥
0. Factor out all squares to obtain the form
m
2
p
i
1
1
p
i
2
2
···p
i
k
k
, where
m ∈ N and i
j
= 0 or 1.
Let
N ∈ N
. Given any number
x ≤ N
, when put in the above form, we have
m ≤
√
N
. So there are at most
√
N
possible values of
m
. For each
m
, there
are 2
k
numbers of the form
m
2
p
i
1
1
p
i
2
2
···p
i
k
k
. So there are only
√
N ×
2
k
possible
values of x of this kind.
Now pick
N ≥
4
k
. Then
N >
√
N ×
2
k
. So there must be a number
≤ N
not of this form, i.e. it has a prime factor not in this list.
Historically, many people have came up with “new” proofs that there are
infinitely many primes. However, most of these proofs were just Euclid’s proof
in disguise. Erd¨os’ proof is genuinely a new proof. For example, Euclid’s proof
comes up with a particular number
N
, and says all its factors are not in the
list of primes. On the other hand, Erd¨os’ proof says that there is some number,
which we don’t know, with at least one factor not in the list.
Also, the proofs give different bounds on when we should expect to see the
k
th prime. For example, Euclid tells us that the
k
th prime must be less than
2
2
k
, while Erd¨os tells us it is less than 4
k
.
Theorem. If a | bc and (a, b) = 1, then a | c.
Proof.
From Euclid’s algorithm, there exist integers
u, v ∈ Z
such that
ua
+
vb
= 1.
So multiplying by c, we have uac + vbc = c. Since a | bc, a |LHS. So a | c.
Definition (Coprime numbers). We say a, b are coprime if (a, b) = 1.
Corollary. If p is a prime and p | ab, then p | a or p | b. (True for all p, a, b)
Proof.
We know that (
p, a
) =
p
or 1 because
p
is a prime. If (
p, a
) =
p
, then
p | a. Otherwise, (p, a) = 1 and p | b by the theorem above.
Corollary. If p is a prime and p | n
1
n
2
···n
i
, then p | n
i
for some i.
Note that when we defined primes, we defined it in terms of factors of
p
.
This corollary is the opposite — it is about how
p
behaves as a factor of other
numbers.
Theorem
(Fundamental Theorem of Arithmetic)
.
Every natural number is
expressible as a product of primes in exactly one way. In particular, if
p
1
p
2
···p
k
=
q
1
q
2
···q
l
, where
p
i
, q
i
are primes but not necessarily distinct,
then k = l. q
1
, ···q
l
are p
1
, ···p
k
in some order.
Proof.
Since we already showed that there is at least one way above, we only
need to show uniqueness.
Let
p
1
···p
k
=
q
1
···q
l
. We know that
p
1
| q
1
···q
l
. Then
p
1
| q
1
(
q
2
q
3
···q
l
).
Thus
p
1
| q
i
for some
i
. wlog assume
i
= 1. Then
p
1
=
q
1
since both are primes.
Thus p
2
p
3
···p
k
= q
2
q
3
···q
l
. Likewise, we have p
2
= q
2
, ··· and so on.
Corollary.
If
a
=
p
i
1
1
p
i
2
2
···p
i
r
r
and
b
=
p
j
1
1
p
j
2
2
···p
j
r
r
, where
p
i
are distinct primes
(exponents can be zero). Then (
a, b
) =
Q
p
min{i
k
,j
k
}
k
. Likewise,
lcm
(
a, b
) =
Q
p
max{i
k
,j
k
}
k
. We have hcf(a, b) × lcm(a, b) = ab.
However, this is not an efficient way to calculate (
a, b
), since prime factoriza-
tion is very hard.
Note that this is a property peculiar to natural numbers. There are “arith-
metical systems” (permitting addition, multiplication and subtraction) where
factorization is not unique, e.g. even numbers.
Example. The following systems have no prime unique factorization
(i)
Even numbers. “Primes” are twice of odd numbers. So 6 is a prime (NOT
divisible by 2!) while 8 is not. We have 60 = 2
×
30 = 6
×
10, where
2
,
6
,
10
,
30 are primes. However, this example is not “proper” since there
is no identity element. (i.e. not a ring)
(ii)
Consider
Z
[
√
−5
] =
{a
+
b
√
−5
:
a, b ∈ Z}
. We have 6 = 2
×
3 =
(1
−
√
−5
)(1+
√
−5
). It can be shown that these are primes (see IB Groups,
Rings and Modules).
Exercise: Where does the proof of the Fundamental Theorem of Arithmetic
fail in these examples?