Lucasian Criteria for the Primality of Repunit numbers

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 .

• Why is it interesting? – user6976 Apr 20 '12 at 8:03
• @MarkSapir Because this test is fast and deterministic... – pedja Apr 20 '12 at 8:11
• No it is not deterministic. Because you cannot prove that the test is correct. And checking your claim for the five primes among the repunits is ridiculous because the converse, which is the nontrivial part of your conjecture, can only fail for nonprimes. A possible approach for proving this conjecture is the following: show that there are only five repunit primes, and verify the conjecture in each case. Good luck. – Franz Lemmermeyer Apr 20 '12 at 10:10
• @FranzLemmermeyer You can formulate same criterion for Mersenne numbers if you set $S_i=P_2(S_{i-1})$ , $S_0=34$ , and $n>5$ – pedja Apr 20 '12 at 10:31
• @MarkSapir Starting seed $S_0$ isn't chosen randomly... – pedja Apr 20 '12 at 12:55

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

• Welcome, Rene! If you click on pedja's name you will see that he likes to ask the same type of question over and over again. My point was (as is yours) that the standard primality tests are based on factorizations of n-1 and n+1, and that you can do similar things if you can factor Phi(n) for other cyclotomic polynomials. Since there is no such factorization in the repunit case, there is no hope of proving this conjecture (or any of the others pedja has put forth) with known methods. And he's been told this same thing over and over again, but to no avail. Which perhaps explains my "approach". – Franz Lemmermeyer Apr 21 '12 at 16:00