MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Return to Answer

2 added 2074 characters in body

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 providesuch 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 provethat 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 shapeof 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 somealgebraic 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 theclassical 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/LucasLehmer_primality_test

1

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