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ˇıˇ 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
Previous Page Next Page