Problems & Puzzles: Puzzles

Puzzle 239. psp (2) & n² -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:

Conjecture: There exist no pseudoprime (in any base, hence no Carmichael number) of the form n²-2 where n is an integer. Therefore, the Fermat test is valid to prove the primality of all the numbers of the form n²-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 n²-2" then the statement is false, no doubt. Examples:

• 287 = 17^2 - 2 = 7*41 is pseudoprime for the base a=41          (41²⁸⁷=41 mod 287)
• 322 = 18^2 - 2 = 2*7*23 is pseudoprime for the base a=23       (23³²²=23 mod 322)

2. If the Leleu's statement says that "there is no pseudoprime, base a=2, of the form n²-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 n²-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 n²-2, for n²-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 n² - 2, then the Fermat test could be used as a valid test to prove the primality of the odd numbers of the form n² -2

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

So, the questions are:

1. Can you find an odd n value such that n² - 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?  b) what is the earliest psp(2) of the form n² -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.

"... 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: http://groups.yahoo.com/group/primeform/message/3766  

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:

***

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, (83²⁸⁶=1 mod 287)
• 322 = 18^2 - 2 = 2*7*23 is pseudoprime for the base a=277, (277³²¹=1 mod 322)

***