Lucasian Criteria for the Primality of Repunit numbers

2012-04-20T07:37:19Z

Def 1.

Let's define repunit number $R_n$ in base $10$ as :

$R_n=\frac{10^n-1}{9}$ , with $n \geq 1$

Def 2.

Next , define polynomial $P_n(x)$ as :

$P_n(x)=2^{-n} \cdot \left(\left (x-\sqrt{x^2-4} \right )^n+\left (x+\sqrt{x^2-4}\right )^n \right )$

Def 3.

Let's define sequence $S_i$ as :

$S_i=P_{10}(S_{i-1})$ with $S_0=15127$

Conjecture :

$R_n ; (n > 5) ~\text{is a prime iff }~ S_{n-1}\equiv S_0 \pmod {R_n} $

I have checked statement for following repunit primes :

$R_{19} , R_{23} , R_{317} , R_{1031} , R_{49081} $

Question :

I am interested in approaches which can be used to prove this conjecture .

P.S.

One can formulate similar conjectures for repunits in all other bases .

Answer by Rene Schoof for Lucasian Criteria for the Primality of Repunit numbers

2012-04-20T18:30:46Z

The number $15127$ is of course the trace of the $20$-th power of the golden ratio ...

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.
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.

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 prove that repunits that do not pass the test, are not prime.

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.

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.

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$.

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.

Ref: http://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test

Lucasian Criteria for the Primality of Repunit numbers - MathOverflow

Lucasian Criteria for the Primality of Repunit numbers

Answer by Rene Schoof for Lucasian Criteria for the Primality of Repunit numbers