40 1. Elementary Prime Number Theory, I
For each p ∈ P, set vp := supk≥1 vp,k. We let P1 := {p ∈ P : vp
∞} and we put P2 := P \ P1. Show that if p ∈ P2, then p a.
(b) Suppose p ∈ P2, and let lp be the order of a modulo p. (This exists
by part (a).) Define ep so that
pep alp
− 1. Show that if k is a
positive integer for which
pep+1
|
ak
− b, then k belongs to a fixed
residue class modulo p.
(c) Show that there is an infinite arithmetic progression of integers k
which avoid all the residue classes mod p (p ∈ P2) determined in
(b). Prove that
ak−b
is uniformly bounded for such k, contradicting
that
|ak
− b| → ∞ as k → ∞.
Remark. In the opposite direction, one can ask when the set P defined
above omits infinitely many primes. Using the Chebotarev density the-
orem, Schinzel [Sch60] has shown that this holds unless b =
ak
for some
nonnegative integer k. See also [MS00].
22. (Kˇıˇ r´ zek et al. [KLS02]) Let Fn =
22n
+ 1 be the nth Fermat number.
Suppose N ∈ N.
(a) Show that there are fewer than
2N
distinct prime divisors of the
product F0 · · · FN−1.
(b) Show that for each x 0, the number of primes p ≤ x which divide
Fn for some n ≥ N is at most
x/2N+1.
(c) Making an appropriate choice of N, deduce from (a) and (b) that
there are
√
x primes p ≤ x which divide a term of the sequence
F0,F1,F2,....
(d) Deduce that if λ 1/2, then
∑
p−λ
∞, where the indi-
cates that the sum is restricted to primes dividing at least one
Fermat number. When λ = 1, this confirms a conjecture of Golomb
[Gol55].
23. (Erd˝ os & Tur´ an [ET34]) For n 1, write P (n) for the largest prime
factor of n. In this exercise we show that if S is an infinite set of natural
numbers, then
(1.19) {P (a + b) : a, b ∈ S} is unbounded.
For each prime p, let vp be the p-adic valuation, defined so that
pvp(n)
n
for every natural number n.
(a) Let S be an arbitrary infinite set of natural numbers. Show that
for each odd prime p, we can determine an infinite subset S ⊂ S
with the property that whenever a, b ∈ S ,
(1.20) vp(a + b) = min{vp(a),vp(b)}.
Hint: First treat the case when no element of S is divisible by p.
(b) Suppose, for the sake of contradiction, that S is infinite but (1.19)
fails. Using part (a), argue that we may assume (1.20) holds for
