5
$\begingroup$

How to prove that this conjecture about a new primality test for Mersenne numbers is true ?

Definition: Let $M_{q}=2^{q}-1 , S_{0} = 3^{2} + 1/3^{2} , \ and: \ S_{i+1} = S_{i}^{2}-2 \pmod{M_{q}}$

Conjecture: $$M_{q}\text{ is a prime iff: } \ S_{q-1} \equiv S_{0} \pmod{M_{q}}$$ $$\text{ and iff: } \prod_{0}^{q-2} S_i \equiv 1 \pmod{M_{q}}$$ $$\text{ and iff: } S_i \not\equiv S_0 \pmod{M_{q}} , 0 < i < q-1$$

The easy part part (if $M_{q}$ is prime then $S_{q-1}\equiv S_{0} \pmod{M_{q}}$), has already been proven. See: http://tony.reix.free.fr/Mersenne/ConjectureLLTCyclesMersenne.pdf .

Now, a proof of the converse is needed.

The "classic" LLT by Lucas and Lehmer for Mersenne numbers is based on the binary tree of the digraph (under $x^2-2 \pmod{M_q}$). This new conjectured test makes use of a cycle of the same digraph.

The goal of this question is to validate (or not) the method (use a cycle of the digraph) for Wagstaff numbers ($\dfrac{2^q+1}{3}$ , q prime) for which we also lack a proof for the converse. See: https://trex58.files.wordpress.com/2009/01/wagstaffandfermat.pdf for a proof of the easy part, by Robert Gerbicz .

I and a team (Vincent and Paul) had found a very large Wagstaff PRP with this algorithm. See: http://www.primenumbers.net/prptop/prptop.php (2^4031399+1)/3 , rank 9 for now.

Improve this question
$\endgroup$
5
  • $\begingroup$ Does not the criterion amount to the disjunction of $3^{2^{q-1}-1}\equiv\pm1$ and $3^{2^{q-1}+1}\equiv\pm1$ ($\mod{M_q}$)? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Sep 2, 2015 at 5:20
  • $\begingroup$ Hummmm I do not follow you. Would you mind elaborating ? Thanks. $\endgroup$
    – Tony Reix
    Commented Sep 3, 2015 at 16:11
  • $\begingroup$ Well to begin with, $S_i=9^{2^i}+9^{-2^i}$ ($\mod M_q$); so $S_{q-1}-S_0$ is $9^{2^{q-1}}+9^{-2^{q-1}}-9-9^{-1}$ which may be rewritten as$$9^{-2^{q-1}}\left(9^{2^q}-9^{2^{q-1}+1}-9^{2^{q-1}-1}+1\right).$$ This is zero mod $M_q$ (provided $M_q$ is not divisible by $3$) if and only if $9^{2^q}-9^{2^{q-1}+1}-9^{2^{q-1}-1}+1$ is. One may further decompose, it is$$\left(9^{2^{q-1}+1}-1\right)\left(9^{2^{q-1}-1}-1\right)=\left(3^{2^{q-1}+1}-1\right)\left(3^{2^{q-1}+1}+1\right)\left(3^{2^{q-1}-1}-1\right)\left(3^{2^{q-1}-1}+1\right).$$ $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Sep 3, 2015 at 16:29
  • $\begingroup$ Oh yes. Much clearer now. Thanks. Do you think it can help proving the converse of the conjecture ? $\endgroup$
    – Tony Reix
    Commented Sep 3, 2015 at 17:41
  • $\begingroup$ Honestly I don't know. I just meant adding this version might be useful. In case of course if I am not mistaken and it is really equivalent. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Sep 3, 2015 at 18:17

0

Reset to default

You must log in to answer this question.