Problems & Puzzles: Puzzles
Puzzle 239. psp (2) & n2 -2 numbers.
Let's first remember some basic concepts for this puzzle.
Two months ago, Hervé Leleu sent to me the following message:
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:
Just in this last expression I agree with Leleu in the following statement:
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.
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"
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: