Lucasian Criteria for the Primality of Repunit numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T03:11:30Z http://mathoverflow.net/feeds/question/94610 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94610/lucasian-criteria-for-the-primality-of-repunit-numbers Lucasian Criteria for the Primality of Repunit numbers pedja 2012-04-20T07:37:19Z 2012-04-21T12:36:29Z <p><strong>Def 1.</strong></p> <p>Let's define repunit number $R_n$ in base $10$ as :</p> <p>$R_n=\frac{10^n-1}{9}$ , with $n \geq 1$</p> <p><strong>Def 2.</strong></p> <p>Next , define polynomial $P_n(x)$ as :</p> <p>$P_n(x)=2^{-n} \cdot \left(\left (x-\sqrt{x^2-4} \right )^n+\left (x+\sqrt{x^2-4}\right )^n \right )$</p> <p><strong>Def 3.</strong></p> <p>Let's define sequence $S_i$ as :</p> <p>$S_i=P_{10}(S_{i-1})$ with $S_0=15127$</p> <blockquote> <p><strong>Conjecture :</strong></p> <p>$R_n ; (n > 5) ~\text{is a prime iff }~ S_{n-1}\equiv S_0 \pmod {R_n}$</p> </blockquote> <p>I have checked statement for following repunit primes :</p> <p>$R_{19} , R_{23} , R_{317} , R_{1031} , R_{49081}$</p> <p><strong>Question :</strong></p> <p>I am interested in approaches which can be used to prove this conjecture .</p> <p><strong>P.S.</strong></p> <p>One can formulate similar conjectures for repunits in all other bases .</p> http://mathoverflow.net/questions/94610/lucasian-criteria-for-the-primality-of-repunit-numbers/94666#94666 Answer by Rene Schoof for Lucasian Criteria for the Primality of Repunit numbers Rene Schoof 2012-04-20T18:30:46Z 2012-04-21T12:36:29Z <p>The number $15127$ is of course the trace of the $20$-th power of the golden ratio ...</p> <p>I think that trying to find a Lucas-like test for repunits is an interesting problem. It is certainly not true that "standard methods" would test repunits numbers faster for primality than such a Lucas-like test.<br> Indeed, the largest primes known are Mersenne primes, proved prime by the Lucas-Lehmer test. These numbers are far larger than what general purpose primality tests can deal with.</p> <p>However, the algorithm proposed by pedja does not seem to provide such a Lucas-like test. It is easy to prove that a prime repunit passes his test. However, as Franz Lemmermeyer wrote, the point of a Lucas-like test is to <em>prove</em> that repunits that do not pass the test, are not prime. </p> <p>For a given repunit $p$ pedja's algorithm essentially checks that $a^{p-1}\equiv 1$ mod $p$ for some very specific residue $a$ mod $p$ (related to the golden ratio). When $p$ is prime this is of course true. Probably it is always false when $p$ is a repunit that is not prime. However, there is no hope of proving this. That's the point. </p> <p>The classical Lucas-Lehmer test for Mersenne numbers $2^n-1$ exploits the special shape of these numbers. It checks that a certain element $x$ in a certain multiplicative group has order $2^n$. If $2^n-1$ is prime, this must be true. The point of the Lucas-Lehmer test is that, conversely, the fact that $x$ has order $2^n$ proves that $2^n-1$ is prime.</p> <p>A Lucas-Lehmer test for repunits should exhibit an element of order $10^n$ in some algebraic group. I don't see anything like that in pedja's algorithm. Indeed, the algorithm that he/she proposes for Mersenne numbers does not even boil down to the classical Lucas algorithm since the computation takes place in the multiplicative group of integers modulo $2^n-1$, which does not contain any elements of order $2^n$.</p> <p>Final remark: just as for Mersenne primes, there are probably infinitely many prime repunits. So Lemmermeyer's approach for proving pedja's conjecture is not a very good one.</p> <p>Ref: <a href="http://en.wikipedia.org/wiki/Lucas" rel="nofollow">http://en.wikipedia.org/wiki/Lucas</a>–Lehmer_primality_test</p>