# Show that if a positive integer $n$ is composite then $R(n) = \frac{10^{n}-1}{9}= 111…11 (n times)$ is composite [duplicate]

This question already has an answer here:

Show that if a positive integer $n$ is composite then $R(n) = \frac{10^{n}-1}{9}= \underset{n\text{ times}}{\underbrace{111...11}}$ is composite

I attempted a both a normal proof and proof by contradiction by trying:

$n = ak$

show if $ak\equiv 0 \mod a$ then $(10^{ak}-1) \equiv 0\mod (10^a-1)$

I reached a point where I began to go around in cirlces. Maybe I'm going down the wrong track. Any ideas ?

## marked as duplicate by Jyrki Lahtonen, HK Lee, Davide Giraudo, Martin Sleziak, beep-boopOct 10 '14 at 16:36

HINT

\begin{align}10^{ak} - 1 &= (10^a-1)(10^{ak-a} + 10^{ak-2a} + \cdots + 1) \\~\\&= (10-1)(10^{a-1}+10^{a-2}+\cdots+1)(10^{ak-a} + 10^{ak-2a} + \cdots + 1)\end{align}

n is composite, for example n = ab.

If you write 1111...1111 (n digits), you can split this number into a groups of b digits, for example if b = 3

111 111 111 ... 111


Can you just look at this number and tell me a factor? (The factor stares you right in the face).

we may as well keep this algebraic. define the polynomials $P_n(x)$ to be the sum of the first $n$ non-negative integer powers of $x$, so, for example, $P_4(x)=1+x+x^2+x^3$

for any $n$ we have $$(x-1)P_n(x) = x^n -1$$ we also have: $$P_{mn}(x) =P_n(x)P_m(x^n)$$ multiplying both sides by $x-1$ gives your result (set $x=10$)

$(10^n-1)=(1+10+10^2+10^3+...+10^{n-1})(10-1)$

Note that $10-1$ is divisible by $9$.

Can you show that $(1+10+10^2+10^3+...+10^{n-1})$ is composite?

Note that if we have: $1+10+10^2+10^3=1+10+10^2(1+10)=(1+10^2)(1+10)$. Do you see what to do? The number of terms you have is composite. So, you can always factor them in this way.

• I believe that is the original question. – taninamdar Oct 10 '14 at 14:28
• N must be composite, and we must show that R(n) must also be composite. – Gregory Peck Oct 10 '14 at 14:28
• This is fine for $n\geq 2$ – leo Oct 10 '14 at 16:20

If $n$ is composite, we can write $n = ab$ with $a,b\in\mathbb N$.

Define $Q(a,b) = 10\dots010\dots01$, where there are $a$ ones and between every two consecutive ones there are $b - 1$ zeros. Then I claim that $R(n) = Q(a,b)R(b) = Q(b,a)R(a)$. To prove this we will write,

$$Q(a,b) = 1 + 10^b + \cdots + 10^{(a-2)b} + 10^{(a-1)b}\\R(b) = 1 + 10^1 + \cdots + 10^{b-2} + 10^{b-1}$$

Then,

$$Q(a,b)R(b) = 1(1 + \cdots + 10^{b-1}) + 10^b(1 + \cdots + 10^{b-1}) + \cdots\\\cdots+ 10^{(a-1)b}(1+\cdots+10^{b-1})$$

Opening parentheses it's easy to see then that $Q(a,b)R(b) = R(n)$, and the second equality follows by symmetry of $Q$'s arguments and symmetry in the definition of $a$ and $b$.

You can prove more generally the following simple result:

Lemma if $m|n$ then $R(m)|R(n)$.

Proof Let $n=am$. Then $$10^{n}-1=(10^m)^a-1=(10^m-1)(\mbox{junk})$$

Therefore $10^m-1|10^n-1$ which implies that $9R(m)|9R(n)$. It is easy to prove that this implies our claim.

R(1)=1

R(2)=11

R(3)=111

R of n is a function for the number of digits in a natural number in which each digit is 1. If n is even, the number will be divisible by 11. If n is divisible by 3, the number will be divisible by 3 and by 111. If n is divisible by 5, R(n) is divisible by 11111. If n is divisible by 7, R(n) is divisible by 1111111, which has 7 digits, all of which are 1. Let p be any prime and substitute p for n. If n is divisible by $p$, then R($p$) is divisible by a number which has $p$ digits, each of which is 1.

• Check that $111111$ is not divisible by $9$. – taninamdar Oct 10 '14 at 14:25
• I cancelled out the 9's to show that if a|n then R(a)|R(n) – Gregory Peck Oct 10 '14 at 14:25
• We have to show that it's composite – Gregory Peck Oct 10 '14 at 14:31