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

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.

...

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  Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.