Definition. An integer n greater than 1 is prime if the only positive divisors of n are 1 and n.
A positive integer n which has a positive divisor other than 1 or n is composite.
People are often puzzled by the fact that 1 is not considered to be prime. Excluding 1 is a convention which makes other things more convenient (such as the statement of the Fundamental Theorem of Arithmetic).
Example. ( Small prime
numbers and composite numbers) List the prime and composite
numbers in the set .
Primes:
Composite numbers:
Lemma. Every integer greater than 1 is divisible by a prime number.
Proof. The result is true for 2, since 2 is
prime and .
Let , and suppose the result is true for all positive
integers greater than 1 and less than n. I want to show that n is
divisible by a prime number.
If n is prime, then n is divisible by a prime number --- itself.
If n isn't prime, then it's composite. Therefore, n has a positive
divisor m such that and
. Plainly, m can't
be larger than n, so
. By induction, m is divisible by
some prime number p. Now
and
, so
. This proves that n is divisible
by a prime number, and completes the induction step. Hence, then
result is true for all integers greater than 1 by induction.
You've probably seen the classical proof of the next result, which goes back to Euclid. Well, in case you haven't (or you've forgotten), here it is.
Theorem. There are infinitely many prime numbers.
Proof. Suppose on the contrary that there were
only finitely many primes ,
, ...
. Every integer greater than 1 is either prime --- so
it's one of the p's --- or it's composite, and by the preceding
lemma, divisible by one of the p's.
Consider the number . m leaves a
remainder of 1 when it's divided by
,
, ...
. Therefore, it's not composite.
But it can't be one of the primes, since it's larger than all of the
p's. This is a contradiction, so there must be infinitely many
primes.
Prime numbers used to be a mathematical curiosity. In the last few decades, they've found important applications --- for example, to the field of cryptography. But there's still a lot to be curious about.
Question. ( Goldbach's conjecture) Can every even integer greater than 4 be expressed as the sum of two primes?
Goldbach's conjecture has been verified for even numbers up to around
.
Question. ( Twin Prime conjecture) Twin primes are prime number which are 2 units apart (such as 5 and 7). Are there infinitely many twin primes?
The largest known twin primes as of this writing are . They have
digits.
Question. A Mersenne
prime is a prime number of the form , where n is a positive integer (such as
). Are there infinitely many Mersenne primes?
The Mersenne prime is the
largest known prime number as of January, 2018. It was discovered on
December 26, 2017 by Jonathan Pace as a part of GIMPS (the Great
Internet Mersenne Prime Search:
www.mersenne.org). It has
decimal
digits.
Lemma. Suppose p is prime. Then p is
relatively prime to a if and only if .
Proof. Suppose that . I want to show that
. Suppose on
the contrary that
. Since
, p is a common divisor of p and a. Therefore,
. This is a contradiction, since p is
prime.
Conversely, suppose . I want to show that
.
Now , and the only positive numbers that divide
p and 1 and p. Therefore,
or
.
Suppose . Then
, which
contradicts my assumption that
.
Therefore, , so
.
Theorem. ( Euclid's
lemma) Let p be prime, and suppose . Then
or
.
Proof. Let p be prime, and suppose . To show that
or
, I'll assume that
and prove that
.
Since , the preceding result says that
. Therefore, I can find integers m and n such that
Multiply by b:
, and by assumption
, so
. Therefore,
, which is what I wanted to prove.
Remarks. 1. There is a general version of
Euclid's lemma: If p is prime and ,
then p divides at least one of the a's.
2. If p and q are primes and , then
. (Only 1 and q divide q, and p isn't 1, so it must
be q.) Using this fact and the general version of Euclid's lemma, you
can show that if p and q are primes,
, and
, then
.
Example. ( Using Euclid's
lemma to prove a divisibility statement) Prove that if p is
prime and , then
.
Since , Euclid's lemma implies that
or
. Hence,
.
Try writing out the induction proof that shows that if p is prime,
, and
, then
.
Example. ( A problem on
primes and squares) For what prime numbers p is a perfect square?
Suppose , where
. First, if
, then
, so
. Since p is prime, it is
positive, and this is a contradiction.
Therefore, , and I may assume without loss of
generality that x is positive: If x is negative, then
is positive, and
holds.
Thus, I'm now assuming that .
I'll rule out another special case: If , I have
, or
. Since p is prime,
, so this is impossible.
Now I can assume that . This means that
. Moreover,
, so
. In other words,
and
are positive numbers.
Now I'll proceed with the main part of the proof. I have
This says that and
are
positive factors of
. Since 13 and p are prime, the
only positive factors of
are 1, p, 13, and
. There are four cases.
Suppose that and
. The first equation gives
, so
. This contradicts the fact that p
is prime.
Suppose that and
. The first equation gives
, so
. 11 is prime, and
.
Suppose that and
. The second equation gives
, but I'm assuming
. This contradiction
rules out this case.
Finally, suppose that and
. The first equation gives
, which yields
in the second
equation. But p is prime, so
, and
. Thus,
can't equal 3, and this
contradiction rules out this case.
Thus, the only prime p for which is a perfect
square is
.
Theorem. ( The Fundamental
Theorem of Arithmetic) Let n be an integer, . Then n can be written as a product of prime
numbers, and this product is unique up to the order of the factors.
"Up to the order of the factors" means that and
are considered to be "the
same" factorization of 6.
Proof. First, I'll show that every integer greater than 1 can be factored into a product of primes.
I'll use induction. Start with ; this is prime, so
the result holds for
.
Next, let , and suppose every integer greater than 1
and less than n can be factored into a product of primes. If n is
prime, then n is a product of primes (namely, itself), and I'm done.
Otherwise, n is composite. This implies that there are integers a and
b with such that
. Since a and b are
between 1 and n, each of them can be factored into a product of
primes, by the induction hypothesis. Then
shows that the same is true of n.
By induction, every integer greater than 1 can be factored into a product of primes.
Next, I want to show that the prime factorization of a positive integer is unique, up to the order of the factors.
Suppose I have two prime factorizations of the same number:
Thus, the p's and q's are primes, all the p's are distinct and all the q's are distinct (but some p's may be q's, and vice versa), and all the exponents are positive.
Start with . It's prime, and it divides the left side,
so it divides the right side:
By the general version of Euclid's lemma, must divide some
. I can assume
(because if
divided one of the
other q-powers, I could stop and rename everything so the
one it divides is
). By the second remark following
Euclid's lemma, this implies
.
Now the equation looks like this:
I cancel as many 's off both sides as I can. Suppose I wind
up with some left-over
's on the right:
Now I repeat the divisibility argument. divides the right side, so it divides the left side
. As before, this means that
is one of
, ...,
. This is a contradiction, because I assumed at the
start that the p's were distinct.
This means that there can't be any left-over 's on the right, and a similar argument shows that
there can't be any left-over
's on the left. Hence,
all the
's must have cancelled, and I have
I continue in this way, matching up prime powers on the two sides.
Eventually, everything must match up (just as and
did), which shows that the two
original factorizations were identical.
This proves that the prime factorization of an integer is unique, up
to order.
Example. ( Factoring a number into primes) Apply the Fundamental Theorem of Arithmetic to 3768.
I can do this by trial division:
(157 is prime, so that's where I stop.) Therefore, .
Trial division is not a useful way of factoring numbers once they get too large. In general factoring big integers is a hard problem involving many sophisticated methods.
Definition. If m and n are positive integers,
the least common multiple of m and n is the
smallest positive integer which is divisible by both m and n. The
least common multiple of m and n is denoted .
Example. ( Least common
multiples) (a) Compute .
(b) Suppose p and q are distinct primes. Compute .
(a) , since
and
, and no smaller positive integer is divisible by
both 24 and 16.
(b) The least common multiple of and
is
, since it's clearly the smallest
power of p divisible by both
and
. You can see that for two positive powers of a
prime, their least common multiple is the largest of the two powers.
So for
and
, the least common multiple is
. Hence,
.
The prime factorization of a number provides a way of visualizing greatest common divisors and least common multiples.
Example. ( Finding greatest common divisors and least common multiples using prime factorizations) Represent the greatest common divisor and least common multiple of 120 and 280 by drawing a Venn diagram involving their prime factorizations.
Note that
Arrange the prime factors of the two numbers in a Venn diagram:
The factors 2, 2, 2, and 5 are common to the two numbers. They go in
the intersection (shaded), and their product is equal to the greatest common
divisor
.
The least common multiple is the product of all the
numbers in the diagram (counted once each):
Note that if you multiply 120 and 280, this counts the primes in the
intersection --- whose product is --- twice,
whereas
counts the primes in the intersection once.
It follows that
This is true in general: If m and n are positive integers, then . The argument above isn't a proof, but it
makes the result plausible.
Copyright 2019 by Bruce Ikenaga