Problems & Puzzles: Puzzles

Puzzle 239. psp (2) & n2 -2 numbers.

Let's first remember some basic concepts for this puzzle.

A composite integer p is said to be a Fermat pseudoprime base a [p is a psp(a)] if it passes a Fermat test for some integer a, that is to say if ap = a mod p.

Two months ago, Hervé Leleu sent to me the following message:

Conjecture: There exist no pseudoprime (in any base, hence no Carmichael number) of the form n2-2 where n is an integer. Therefore, the Fermat test is valid to prove the primality of all the numbers of the form n2-2.

Unfortunately this was the unique contact between Leleu and me, so I am publishing this puzzle because I think that there is some interest behind it, no matter if the statement is a kind of defective, or I'm missing something important of the Leleu's idea.

Having said this, let's go on. This is what I think of the Leleu's message/conjecture:

1. If the Leleu's statement says that "there is no pseudoprime, in any base a, of the form n2-2" then the statement is false, no doubt. Examples:

  • 287 = 17^2 - 2 = 7*41 is pseudoprime for the base a=41          (41287=41 mod 287)
  • 322 = 18^2 - 2 = 2*7*23 is pseudoprime for the base a=23       (23322=23 mod 322)

2. If the Leleu's statement says that "there is no pseudoprime, base a=2, of the form n2-2", still the statement is false because I know for sure that there is a counter example (not calculated by me but by others) for an even n2-2 value that it certainly is a pseudoprime base 2.

3. But if the Leleu's statement says that "there is no pseudoprime, base 2, of the form n2-2, for n2-2 = odd", then I must recognize that I don't know any counter example, neither I have calculated one of these.

Just in this last expression I agree with Leleu in the following statement:

If it could be demonstrated that it can not exist odd pseudoprimes base a=2 of the form n2 - 2, then the Fermat test could be used as a valid test to prove the primality of the odd numbers of the form n2 -2

This demonstration would open a way of demonstrate easily (the Fermat test) rigorously the primality of a new class of numbers ( n2 -2)

So, the questions are:

1. Can you find an odd n value such that n2 - 2 is psp(2), or can you find a proof that shows that this target is impossible?n

2. If n is even, a) can you find one psp(2) of the form n2 -2?  b) what is the earliest psp(2) of the form n2 -2


Paul Underwood, Sebastián Martín Ruiz, Faride Firoozbakht and Marcel Martin sent contributions to this puzzle.

Summarizing, no proof of the conjecture has been produced and no counterexample has been found.


Paul Underwood wrote to remind us that the Hervé's Conjecture is a particular case of a more general conjecture that he has exposed and studied previously.

"... my conjecture is on your pages [Paul Underwood's Conjecture. See also and his own and updated presentation of his conjecture here] ...I have always been trying to expand it. Recently, I tried a few quadratic forms including x^2-2*x-1 (x even) which is equal to the familiar (x-1)^2-2. I also tried for instance x^2-x-3. I have for a few years now tried to find an x-PrP polynomial in x. That is the existence of P(x): P(x) is base x Fermat PrP implies P(x) is prime. (conjecture only). Going back to P(x)=x^2-2*x-1=(x-1)^2-2, we can see none of the divisors of P(x) divide (x-1) and it is necessary only to test P(x) divides 2^((P(x)-1)/2)-1.


Please see the thread "x-prp quadratic" at:  

this is connect to my conjecture. David Broadhurst has finally convinced me that a computer search is a waste of time!


Sebastián Martín Ruiz wrote: "No psp(2) of the form n^2-2 for n=1 to 10 000 000 according to my own calculations"


Faride wrote:

There is no odd pseudoprime, base a=2, of the form n^2-2 up to 11000000. All known even numbers n such that n divides 2^n-2,are terms of sequence A006935.

A006935: 2,161038,215326,2568226,3020626,7866046,9115426,49699666,143742226, 161292286,196116194,209665666,213388066,293974066,336408382,377994926, 410857426,665387746,667363522,672655726, 760569694,1066079026,1105826338.

Note that 16 numbers of the 23 terms of this sequence are equal to 6 mod 10, so they couldn't be of the form n^2-2. Only the first term (2) of A006935 is of the form n^2-2,which is prime not pseudoprime.


Thanks to a very friendly and interesting interchange of ideas with Marcel Martin, I would like to make some reconsideration to the concepts posed in the presentation of this puzzle.

1. Only for even p numbers seems to be justified the congruence pseudoprimality criteria expressed above ( p is a psp(a) if ... a^p = a mod p.)

2. For odd p numbers a preferable congruence pseudoprimality criteria should be: p is a psp(a) if ... a^(p-1) = 1 mod p;  gcd(a,p)=1.

3. Accordingly with this, the counterexamples given above (287 & 322) are not the most convenient and is better to change them to the following ones:

  • 287 = 17^2 - 2 = 7*41 is pseudoprime for the base a=83, (83286=1 mod 287)
  • 322 = 18^2 - 2 = 2*7*23 is pseudoprime for the base a=277, (277321=1 mod 322)



Records   |  Conjectures  |  Problems  |  Puzzles