# Show that if $R_n$ is prime then $n$ must be prime.

this is an exam practice question:

For each positive $n$ define $R_n = \frac{1}{9}(10^n-1)$ (so that in the usual base 10 notation, $R_n = 111,\ldots,1$ where there are n digits).

Show that if $R_n$ is prime then $n$ must be prime.

Here is what I have so far:

Suppose that $R_n$ is prime. Let $R_n = p$

$$9 \cdot p=(10^n-1)$$ $$\implies 10^n \equiv 1 \pmod p$$By Fermat's theorem, $$10^{p-1} \equiv 10^n \equiv 1 \pmod p$$

and then if $ord_p(10) = j$, it follows that

$$p-1 \equiv n \pmod j$$

But now I'm not too sure where to go from here. I've tried manipulating and rearranging things but I don't really know what the way forward is from here.

Any help would be greatly appreciated!!

Suppose that $n=ab$, where $a\gt 1, b\gt 1$.

Note that $10^a-1$ is a proper divisor of $10^{ab}-1$. For let $x=10^a$. then $10^{ab}-1=x^b-1=(x-1)(x^{b-1}+x^{b-2}+\cdots +x+1)$.

If $a\gt 1$ and $b\gt 1$ then both $\frac{x-1}{9}$ and $x^{b-1}+x^{b-2}+\cdots +x+1$ are greater than $1$.

For completeness, note that if $n=1$, than $\frac{10^n-1}{9}$ is not prime.

• Hi Andre, if I am following your solution correctly, this shows that if $n$ is composite then $R_n$ is composite. So if $n=p$ a prime, I would be left with $10^{p-1}+10^{p-2}+...+10+1$, wouldn't I then have to show that this is then prime? Is there a way to start with assuming $R_n$ is prime and going in that direction? – JackReacher Nov 9 '13 at 3:16
• You are asked to show that if $R_n$ is prime, then $n$ is prime. We showed precisely that, by showing that if $n$ is non-prime, then $R_n$ cannot be prime. You were not asked to show that if $n$ is prime, then $R_n$ is prime. For one thing, that is false. We have $R_3=111$, not prime. I believe it is not known whether there are infinitely many primes $p$ such that $R_p$ is prime. – André Nicolas Nov 9 '13 at 3:26
• Many Thanks Andre, I think I understand (just had to get my head around the logic a bit!). By the way, how did you get that $10^a-1$ is a proper divisor of $10^{ab}-1$? I'm assuming this is a pretty basic lemma? To be respectful of your time, could you just point me to where I can read about it? Many thanks again! – JackReacher Nov 9 '13 at 3:35
• It is contained in the formula $x^b-1=(x-1)(x^{b-1}+\cdots+1)$. Here $x=10^a$. Each of $x-1$ and $x^{b-1}+\cdots+1$ is greater than $1$. And yes, as to the logic, we showed that $A\implies B$ by showing the equivalent $\lnot B\implies \lnot A$. Or else one could say we proved it by contradiction. suppose that $n$ is not prime; we showed that $R_n$ cannot be prime. – André Nicolas Nov 9 '13 at 3:39

Here's an example factorisation of R_15:

111111111111111 = 11111 * 10000100001

I think it is obvious that this generalises. André's proof uses exactly this factorisation.