0
$\begingroup$

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 ?

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

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}$$

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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$)

$\endgroup$
2
$\begingroup$

$(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.

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

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$.


This article should be relevant.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

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