Math Central - mathcentral.uregina.ca
Problem of the Month
 Currentproblem Recent problemswith solutions
 Older problems from 2005/2006 06/07 07/08 08/09 09/10 10/11 11/12

Solution for October 2010

 The Problem: Find all primes p such that 2p + p2 is also a prime.

Correct responses:

Correct solutions to our October problem were submitted by

 Bojan Bašić (Serbia) Sergey Gleizer (USA) Roopesh Mangal (Malaysia) Luigi Bernardini (Italy) Bruce Golfman (Austria) Remo Mantovanelli (Italy) José Borges (Portugal) Cornel Gruian (Romania) Milan Pavic (Serbia) Lou Cairoli (USA) Verena Haider (Austria) Benjamin Phillabaum Bernard Collignon (France) Tom Holens (Manitoba) Christian Pont (France) Shai Covo (Israel) Benoît Humbert (France) Shpetim Rexhepi (Macedonia) Zdravko Cvetkovski (Macedonia) Kipp Johnson (USA) John T. Robinson (USA) Dan Dima (Romania) Wolfgang Kais (Germany) Elon Smith (USA) Daniel Drob (Québec) Bushra Khawaja (Regina) Albert Stadler (Switzerland) Allen Druze (USA) Mehdi Kolahchi (Canada) Damian Straszak (Poland) Sébastien Dumortier (France) Jinzhong Li (China) Jan van Delden (The Netherlands) Mei-Hui Fang (Austria) Matthew Lim (USA) Paul Voyer (France) Philippe Fondanaiche (France) Daniel Lopez Aguayo (Mexico)

The solution:

Answer.  p must be 3; more precisely, if p is a prime number, then f(p) = 2p + p2 is also prime if and only if p = 3.

Most of the submitted solutions were based on computations involving integers modulo 3, as follows.  Readers who are unhappy with modular arithmetic can skip to the end where we look at an alternative approach.
Proof.
When p = 2, f(2) = 4 + 4 = 8, which is not prime; when p = 3, f(3) = 8 + 9 = 17, which is prime.  It remains to show that for primes greater than 3, f(p) is a proper multiple of 3.
Let p be any prime number greater than 3.  Since 2 ≡ –1 (mod 3) and p is odd,

2p ≡ (-1)p ≡ -1 (mod 3).

Since we take p > 3 and prime, p ≡ ±1 (mod 3) (because it cannot be 0 (mod 3)), whence

p2 ≡ (±1)2 ≡ 1 (mod 3).

We conclude that f(p) = 2p + p2 ≡ -1 + 1 ≡ 0 (mod 3); that is, for primes greater than 3, 2p + p2 is divisible by 3.  Since f(p) > 3 and is divisible by 3, it is therefore not prime.

Generalizations.  Two of our correspondents observed that the above argument makes little use of p being prime.  With no extra effort Straszak proved, more generally, that

if n is odd and not divisible by 3, then f(n) = 2p + p2 ≡ 0 (mod 3).

In other words, when n is not divisible by 3, f(n) is divisible by 3.  But we have also, when n is even so is f(n).  Thus, the only way 2p + p2 can be prime is for n to be an odd multiple of 3 or for n = 1 (in which case f(1) = 3).  We compute that f(9) = 593, which is prime; and so are f(15) and f(21).  But the pattern does not continue:

f(27) = 73·521·3529

is not prime; when n > 1 it follows that for f(n) to be prime, it is necessary that n be an odd multiple of 3, but not sufficient.  Of course our problem is the special case when n is prime — 3 is the only prime that is an odd multiple of 3.

Lim proved that what works for 3, works also for an arbitrary odd prime:

If q > 2 is prime, then for any odd n that is not a multiple of q, q divides

g(n) = (q - 1)n + nq-1.

Here q – 1 ≡ –1 (mod q), while nq – 1 ≡ 1 (mod q) by Fermat's little theorem; thus, in this more general setting g(n) = (q - 1)n + nq-1 ≡ –1 + 1 = 0 (mod q).  We see that the only way g(n) = (q - 1)n + nq-1 could be prime is for n to be 1 (g(1) = q) or an odd multiple of q.  Compare this generalization to our problem from April 2004 (where q = 5).

Alternative proof.  We conclude with an argument that avoids modular arithmetic.  Here is the way Kais proved that when p > 3 is prime, f(p) is divisible by 3.  Because

2p + p2 = (2p - 2) + 3 + (p2 - 1),

it suffices to show that all three summands on the right are divisible by 3.  Since p is a prime number greater than 3, it must be odd so that we can write it as p = 2k + 1 for some positive integer k.  Then,

2p - 2 = 22k+1 - 2 = 2(22k - 1) = 2(4k - 1),

which is divisible by 4 – 1 = 3 because 4k - 1 = (4 - 1)(4k-1 + 4k-2 + ··· + 4 + 1). (Alternatively, one can use induction on k, as Collignon did, to prove that 4k = 3K + 1 for some integer K.)  Since 3 is by definition divisible by 3, it remains to show that p2 - 1 is also divisible by 3.  Since by assumption p is not divisible by 3, either p – 1 or p + 1 must be, and therefore so must their product, namely p2 - 1.

 Math Central is supported by the University of Regina and the Pacific Institute for the Mathematical Sciences.
 about math central :: site map :: links :: notre site français