(unproven) Potential new primality conjecture for Mersenne numbers

[Batalov]

Originally Posted by ETLem

As an aside the thread title was changed to "unproven ... conjecture".
That seems a tad redoundant ;-)
How about "A new conjecture about Mersenne Primes".

What made you think that this is a 'new conjecture'?

Your original thread title was false and misleading: 'Potential new primality test for Mersenne numbers'.
One moderator implemented your request to change 'test' to 'conjecture'.
Another added '(unproven)', so that potential readers could save themselves 10+ minutes to read by deciding not to not even being confused by title if what's being offered here.

If I found a thread with this current title I wouldn't have even entered. Now that I have, I want my time back, but at least I can save it for someone else.

[Batalov]

Also, suggestion for simplification of your statement.

Your a=1+√2 (mod p) -- much simpler to look at.
Are you saying that \(a^{{p+1}\over 2} = a\) (mod p) ?
That's the same* as a^p = a (mod p) which is the a-PRP test with a peculiar a value.

_______
*except for implying the + sign of the "square root of the Fermal litttle test". Can the sign be '-' for any odd p values?
If you can follow the Berrizbeitia-Iskra path (test for Gaussian-Mersenne numbers, proven) and actually prove it, then maybe you will have something.

[charybdis]

Originally Posted by Batalov

Can the sign be '-' for any odd p values?

As I'm sure you already know:

For general p, yes it can (eg p=17). For p a Mersenne prime, the answer is "no" for p greater than 7. By Euler's criterion, what we need to show is that a is a square mod p. This is not hard to do using quadratic reciprocity and other basic properties of Jacobi symbols; I will leave this as an exercise for the reader. In the process of solving it you will discover why the test fails for p=7.

[Batalov]

Thank you for answering the rhetorical question.

The '-' sign happens exactly at q=3.
(Which makes a-PRP still work, even for q=3, because you square both sides for the last time in it.)

[Dr Sardonicus]

Originally Posted by ETLem

<snip>
By the way is there known Carmichael number(s) that are also Mersenne number(s)?

Not AFAIK. Probably better to ask whether any Mersenne numbers are Carmichael numbers. I will here restrict this question to prime exponents, since M_n has algebraic factors so is obviously composite when n is composite.

In theory, yes AFAIK. In practice, I wouldn't hold my breath.

Or could it be proven that it exist Mersenne numbers that are also Carmichael numbers?

AFAIK none are known, and all the easy things to check are exclusionary.

If q = 2*k*p + 1 divides M_p, and k does not divide 2^p-1 - 1 (for example, if k is even), then M_p is not a Carmichael number. [Note: If k is even, it is also divisible by 4.]

If M_p is completely factored, and has evenly many factors, at least one factor q = 2*k*p + 1 will have k divisible by 4, so M_p is not a Carmichael number.

If a PRP test says M_p is composite, it is not a Carmichael number. If p is large, a PRP test will AFAIK not "officially" be run on M_p if a factor has been found, though the cofactor will be PRP tested.

For "small" primes p, M_p has been PRP tested to the base 3 whether any factors are known or not, with no composite M_p "passing" the test. So M_p is definitely not a Carmichael number for p up to whatever limit this has been done.

I don't know how many M_p among the "first tested" remain standing as possible candidates for being Carmichael numbers. My guess is, "Not many."