Prime and Repunits

Question

Prove that:

For any integer $n > 5$, if $n$ divides $\dfrac{10^{n-1}-1}{9}$, then $n$ is a prime number.

This can also be generalized further as

If $n$ is an integer > 5 and divides a number made out of $k$ repdigit and if $n$ = 1 mod $k$ then $n$ must be a prime number

I also wonder if computation can be optimized for such a special case and the same can be used for finding prime numbers more quickly.

Answer 1

$91>5,$ and 91 divides $\frac{10^{90}-1}{9},$ but $91=7\cdot13$ is composite.

I discovered this with a quick PARI/GP script

ok(n)=if(n%3,Mod(10,n)^(n-1)==1,Mod(10,9*n)^(n-1)==9)
forcomposite(n=6,1e6, if(ok(n), return(n)))

which, suitably modified, lead me to sequence A000864 in the OEIS. Amusingly enough, these numbers are called the "deceptive (non)primes". The OEIS also gives a reference to a paper in the Missouri Journal of Mathematical Sciences which discusses these numbers. Through the magic of Moore's Law, it takes only seconds to replicate the calculations reported there! I extended the search to $10^9$ on a lark, finding 5210 pseudoprimes. The search took 11 minutes on one core.