Problems & Puzzles: Puzzles Puzzle 239. psp (2) & n^{2} 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 a^{p} = a mod p. 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 ( n^{2} 2) So, the questions are: 1. Can you find an odd n value such that n^{2}  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 n^{2} 2? b) what is the earliest psp(2) of the form n^{2} 2 Solution: 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^22 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^22 up to 11000000. All known even numbers n such that n divides 2^n2,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^22. Only the first term (2) of A006935 is of the form n^22,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^(p1) = 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:
***





