3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – JackReacher Nov 9 '13 at 3:16
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 9 '13 at 3:26
  • $\begingroup$ 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! $\endgroup$ – JackReacher Nov 9 '13 at 3:35
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 9 '13 at 3:39
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.