Exercise Set 2 Solutions: More Prime Numbers

Math 414, Winter 2010, University of Washington

Due Friday (!!), January 22, 2010

1. If f(x) and g(x) are (nonzero) functions, we write f(x) ∼ g(x) to mean that lim_{x→∞} f(x)/g(x) = 1. Prove that for any real number a we have

\frac{log(x)}{x} ∼ \frac{log(x)}{x − a}.

Answer: Taking the quotient this is equivalent to showing that lim_{x→∞}(x− a)/x = 1, which follows from L’Hôpital’s rule or just dividing top and bottom by x.

2. For any polynomial f(x) with integer coefficients, let

P (f) = {f(n) : n ∈ N and f(n) is prime}.

For example,

P (x^{2} + 1) = {2, 5, 17, 37, 101, 197, …}.

Come up with a guess for a condition on f that is equivalent to P (f) containing infinitely many prime numbers. Give evidence for your guess. [Do not worry at all about trying to prove that your guess is correct.] Here is some potentially helpful Sage code, which illustrates computing the number of prime valuesf(n) for f = x^{3} + x − 1 and 1 ≤ n ≤ 100:

   sage: f(x) = x^3 + x - 1
   sage: len([n for n in [1..100] if is_prime(f(n))])
   27

Answer: For degree 1, this is Dirichlet’s theorem, which says that f(x) = ax+b takes on infinitely prime values if and only if gcd(a, b) = 1, i.e., if only if the polynomial f(x) does not factor over ℤ. For degree ≥ 2, we similarly conjecture that f takes on infinitely many primes if it does not factor over ℤ.

3. Let p_{1} = 2, p_{2} = 3, p_{3} = 5, p_{4} = 7, p_{5} = 11, … be the sequence of prime numbers. A prime triplet is three consecutive primes p_{n}, p_{n+1}, p_{n+2} such that p_{n+1} = p_{n} +2 and p_{n+2} = p_{n+1} +2, i.e., p_{n}, p_{n} +2, p_{n} +4 are all prime. For example, 3, 5, 7 are prime triplets. Prove that there are no other prime triplets. [Hint: Suppose p > 3 is a prime and you divide p by 12 and take the remainder r. Then what are the possibilities for r?]

Answer: One of the numbers p, p+2, p+4 must be divisible by 3, since 0, 2, 4 represent all numbers mod 3. The only prime divisible by 3 is the prime 3, so we must have p = 3, as claimed.

Alternatively, for p ≥ 5 we have p (mod 12) is one of 1, 5, 7, 11, since it can’t be anything else or p wouldn’t be prime. But then p, p + 2, p + 4 have residue mod 12 in {1, 5, 7, 11}. But a simple inspection shows that this is impossible for each of p ≡ 1, 5, 7, 11 (mod 12).