42 1. Elementary Prime Number Theory, I

25. (Schinzel [Sch62a]) In 1857, Bunyakovsky conjectured [Bun57] that if

F (T) ∈ Z[T] is an irreducible polynomial with positive leading coeﬃ-

cient and D is the largest positive integer dividing F (n) for each n ∈ Z,

then F (n)/D is prime for infinitely many natural numbers n. Show that

this would follow from Hypothesis H.

26. (Granville; see, e.g., [Mol97, Theorem 2.1]) Assume Hypothesis H.

Show that for every natural number N0, one can find a positive in-

teger A with the property that

n2

+ n + A assumes prime values for all

0 ≤ n ≤ N0. Hint: Apply Hypothesis H to the N0 linear polynomials

T, T +

(12

+ 1),T +

(22

+ 2),...,T + (N0

2

+ N0).

27. (Schinzel & Sierpi´ nski [SS58]) Assume Hypothesis H. Show that if n 1

and r is a positive integer divisible by all primes p ≤ n, then there

are infinitely many arithmetic progressions of length n and common

difference r consisting of consecutive primes.

Remark. The weaker claim that there are arbitrarily long arithmetic

progressions of primes was recently proved in a technical tour de force

by Green & Tao [GT08], using ideas borrowed from ergodic theory (and

several other fields). For some striking elementary consequences of the

Green–Tao result, see [Gra08a].

28. (Cf. Chang & Lih [CL77]) Show that for every N ∈ N, there is a

polynomial F (T) ∈ Z[T] for which {F (k)}k=0

N

is a sequence of N + 1

distinct primes. Hint: For 0 ≤ k ≤ N, put ck(T) =

0≤i≤N,i=k

(T −

i). Using Corollary 1.20, choose integers r0,r1,...,rN for which {1 +

rkck(k)}k=0

N

is a sequence of N + 1 distinct primes. Put F (T) := 1 +

∑N

i=0

rici(T).

29. (Clement [Cle49], Cucurezeanu [Cuc68]) Let k and n be integers with

n k ≥ 2. Suppose that n has no prime divisors k. Show that n and

n + k are simultaneously prime if and only if

k · k!((n − 1)! + 1) + (k! −

(−1)k)n

≡ 0 (mod n(n + k)).

30. (Shanks [Sha64]) Let F (z) =

∑∞

n=0

zn(n+1)/2

and define

G(z) := (F (z) −

1)2

− (F (z) − 1).

Prove that there are infinitely many primes of the form

n2+1

2

(with

n ∈ N) if and only if the power series expansion of G has infinitely

many negative coeﬃcients.

31. Suppose p ≡ 3 (mod 4) is prime. Prove that if 2p +1 is also prime, then

2p + 1 |

2p

− 1. Deduce that Hypothesis H implies Conjecture 1.27.

32. (Selfridge; cf. [Erd50b]) Let n ∈ N. Show that

78557·2n

+1 is divisible

by some prime number from the set {3, 5, 7, 13, 19, 37, 73} . In particular,

78557 ·

2n

+ 1 is always composite.