MATH 223 - Problem Set 4
Due: Friday, October 3 at 5 PM
Questions 1-3,6 are based on the lecture on Thursday, September 25th .
Questions 4-5 are based on the lecture on Monday, September 29th .
Part I
1. Prove that if a, k ∈ N, p is a prime, and p|ak , then p|a
Corollary 2.2 asserts that if
p|a1 a2 . . . ak ,
then p|ai for some 1 ≤ i ≤ k. We have
p|(a · a · . . . · a)
with k copies of a. Hence p|a by Corollary 2.2.
2. (a) For any k ∈ N prove that none of 6k, 6k + 2, 6k + 3, 6k + 4 are prime.
We have
6k = 2 · 3 · k
6k + 2 = 2(3k + 1)
6k + 3 = 3(2k + 1)
6k + 4 = 2(3k + 2),
which in each case, since k is a positive integer, implies that the given
number is composite.
(b) Prove that there are infinitely many primes of the form 6k + 5.
Hint: Find a variant of the proof that there are infinitely many
primes of the form 4q + 3 from the Class Activity on 9/25.
Suppose otherwise. Then there exists finitely many primes pi , 1 ≤
i ≤ k, of the form 6k+5. Consider
m = 6p1 p2 . . . pk − 1.
Claim: m has a prime divisor of the form 6k + 5.
Proof of Claim: Suppose otherwise. First note that since m is odd
2 ∤ m, and since m is of the form 6q − 1, 3 ∤ m. Then, by part (a) all
the prime factors of m must be of the form 6k + 1. But note that for
any k1 , k2 ∈ N.
(6k1 + 1)(6k2 + 1) = 36k1 k2 + 6(k1 + k2 ) + 1 = 6(6k1 k2 + k1 + k2 ) + 1,
It follows that if all the prime factors of a number are of the form
6k+1, then the number itself is as well. This is a contradiction since
m is of the form 6k + 5. This proves the claim.
Thus m has a prime factor of the form 6k + 5 and hence pi | m for
some 1 ≤ i ≤ k. But then pi | m and pi | 6p1 . . . pk , and hence by
Corollary 1.4
pi | 1.
But this is a contradiction since pi > 1. This completes the proof.
3. (a) List the positive divisors of 720 (including 1 and 720 itself). How
many divisors are there?
Ooofff. There are 30 in total. They are:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60,
72, 80, 90, 120, 144, 180, 240, 360, and 720.
(b) Factor your answer to part (a), and also compute the prime factor-
ization of 720 in the form
720 = pe11 . . . pekk .
Any conjectures?
30 = 2 × 3 × 5.
720 = 24 32 51
Any conjectures? Not really. But maybe we just multiply the primes
that appear in the prime factorization of 720 to get 30.
(c) Repeat (a) and (b) for 108. Are the results consistent with your
conjecture from part (b)? If not, can you revise your conjecture so
that it works for both 720 and 108? Your conjecture should have the
form:
“The number of positive divisors of n = pf11 . . . pfℓ ℓ is . . . ”
108 has 12 divisors. They are: 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, and
108.
We have:
12 = 22 31 ,
and
108 = 22 33
My first conjecture is false, but now I have another conjecture: If
n = pf11 . . . pfℓ ℓ , then the number of positive divisors is
(f1 + 1)(f2 + 1) . . . (fℓ + 1).
(d) Prove your conjecture.
Let n = pf11 . . . pfℓ ℓ . Each divisor is of the form
wℓ
d = pw
1 . . . pℓ , where 0 ≤ wi ≤ fi .
1
There are fi + 1 ways to choose wi , and thus
(f1 + 1)(f2 + 1) . . . (fℓ + 1)
ways to choose d. Note that different choices of the wi′ s give different
divisors because of the Fundamental Theorem of Arithmetic.
Part II
Please submit your answers to Part II on a separate piece of paper.
n
4. (a) For n ≥ 0, the Fermat numbers are defined by Fn = 22 + 1. Prove
that for any n ≥ 1,
Fn = (Fn−1 − 1)2 + 1.
Let n ≥ 1. Then
n−1
(Fn−1 − 1)2 + 1 = ([22 + 1] − 1)2 + 1
n−1
= (22 )2 + 1
n−1
= 22·2 +1
2n
=2 +1
= Fn
(b) Using the result of (a), show that for every n ≥ 2, the last digit of
Fn is 7.
We prove the result by induction on n.
Base Case: The base case is n = 2, and F2 = 17. Done.
Inductive Hypothesis: For n ≥ 3 assume Fn−1 has a last digit of 7.
Since Fn−1 ends is a 7, Fn−1 − 1 = 10q + 6 for some q ∈ Z. Then
(Fn−1 − 1)2 = 100q 2 + 120q + 36 = 10(10q 2 + 12q + 3) + 6,
which implies (Fn−1 − 1)2 ends in a 6. Thus
Fn = (Fn−1 − 1)2 + 1
ends in a 7, as required.
5. A “perfect” number is a number n, whose positive divisors less than n
sum to n. For example, 6 is perfect since 6 = 1 + 2 + 3. Prove that if
2p − 1 is a Mersenne prime, then
m = 2p−1 (2p − 1)
is perfect.
Note that m is a power of 2 times a prime. Thus the divisors of m
1, 2, 22 , . . . , 2p−1 as well as 2p − 1, 2(2p − 1), 22 (2p − 1), . . . , 2p−2 (2p − 1).
The sum of the first group of terms is
1 + 2 + 22 + . . . + 2p−1 = 2p − 1,
and for the second set of terms we get
2p − 1 + 2(2p − 1) + 22 (2p − 1) + . . . + 2p−2 (2p − 1) = (2p − 1)(1 + 2 + 22 + . . . + 2p−2 )
= (2p − 1)(2p−1 − 1)
Adding these two terms together we get
2p − 1 + (2p − 1)(2p−1 − 1) = (2p − 1)(1 + 2p−1 − 1)
= 2p−1 (2p − 1)
= m.
Thus m is perfect.
6. (Bonus: 5 pts) Recall that the Prime Number Theorem asserts that if
π(x) is the number of primes p ≤ x, then
π(x)
lim = 1.
x→∞ ( lnxx )
It can also be shown (you don’t have to prove this) that for any k > 0,
that
π((1 + k)x) − π(x)
lim = k.
x→∞ ( lnxx )
(a) Given any k > 0 show that there exists N ∈ N such that if n ≥ N ,
then there is at least one prime p with n ≤ p ≤ (1 + k)n.
Let k > 0. Consider the limit
π((1 + k)x) − π(x)
lim = k.
x→∞ ( lnxx )
Since the denominator goes to infinity, and the limit exists and is
positive, it follows that the numerator goes to infinity also, i.e.
lim π((1 + k)x) − π(x) DNE (+∞).
x→∞
Thus there exists N > 0 such that whenever n > N we have
π((1 + k)n) − π(n) ≥ 1.
It follows that whenever n > N there exists at least one prime in the
interval [n, n(1 + k)].
(b) Let a1 , ..., ad be any sequence of digits, that is,
ai ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} for each 1 ≤ i ≤ d, and a1 ̸= 0.
Prove that there are infinitely many primes whose first (leading) d
digits are a1 , ..., ad .
Hint: Use part (a) with k = 10−d .
Let d and ai for 1 ≤ i ≤ d be as in the question. Following the hint let
k = 10−d , and let N ∈ N be the constant found in part (a).
Choose k0 such that
a1 a2 . . . ad × 10k0 > N.
Then for every natural number s > max(k0 , d) there exists a prime number
between
a1 a2 . . . ad × 10s and a1 a2 . . . ad × 10s × (1 + 10−d ).
We now have
a1 a2 . . . ad × 10s × (1 + 10−d ) = (a1 a2 . . . ad × 10s ) + (a1 a2 . . . ad × 10s−d ),
and since
a1 a2 . . . ad × 10s−d
has exactly s digits. But a1 a2 . . . ad × 10s has s + d digits. Thus
a1 a2 . . . ad × 10s × (1 + 10−d )
has the same first d digits as
a1 a2 . . . ad × 10s .
Finally, note that the primes found for different values of s are distinct.
Indeed, if s1 ̸= s2 , then the primes found above for s1 and s2 have d + s1
and d + s2 digits respectively, and hence are different. Since we have
infinitely many natural numbers s > max(k0 , d) we get infinitely many
distinct primes each of which starts with a1 a2 . . . ad .