Let $R_n = \underbrace{11\ldots1}_{n}$. Prove that if $(n, m) = 1$, then $(R_n, R_m) = 1$.

Question

Let $R_n = \underbrace{11\ldots1}_{n}$.

1) Prove that if $n \mid m$, then $R_n \mid R_m$.

2) Prove that if $(n, m) = 1$, then $(R_n, R_m) = 1$.

I have solved only the first task:

$$m = nk \Rightarrow R_m = \underbrace{11\ldots1}_{nk}\\ R_m = R_n \cdot \underbrace{1\underbrace{00\ldots0}_{n-1}1\underbrace{00\ldots0}_{n-1}1 \ldots 1\underbrace{00\ldots0}_{n-1}1}_{k \mbox{ of } 1}$$

Using the sum of geometric progressions, we can write that $R_n = \frac{10^n-1}{9}$. But I don't know how to continue the second task. Can you help me solve it? Thanks!

Answer 1

1) Write $m=nk$ then $$10^m-1 =10^{nk}-1 = (10^n-1)\Big((10^n)^{k-1}+...+10^n+1\Big)$$ so $$10^n-1\mid 10^m-1\implies R_n\mid R_m$$

Hint for 2):

Use the fact that $$\gcd(a^n-1,a^m-1)= a^{\gcd (m,n)}-1$$

Answer 2

Let $d\mid m$ and $d\mid n,$ so that $m=dj$ and $n=dk$ for some positive integers $j,k.$ Now, note that, for example, $$R_m=\frac{10^{dj}-1}9=\frac{\left(10^d\right)^j-1^j}9=\frac{10^d-1}9\cdot\sum_{i=0}^{j-1}\left(10^d\right)^i=R_d\cdot\sum_{i=0}^{j-1}\left(10^d\right)^i,$$ so that $R_d\mid R_m,$ and likewise, $R_d\mid R_n.$ (Incidentally, this is a more rigorous way to prove your first claim.) In particular, this holds true when $d=\gcd(m,n).$ On the other hand, we can show that if $d\mid R_m$ and $d\mid R_n,$ then $d\mid R_{\gcd(m,n)},$ so that $$R_{\gcd(m,n)}=\gcd\left(R_m,R_n\right).$$ What can we then conclude?

Answer 3

Let $\gcd(R_n, R_m) = d$.

So $\gcd(R_n,R_m) = \gcd(\frac{10^n-1}9, \frac {10^m-1}9) =\frac 19\gcd(10^n-1, 10^m - 1)$

and

$\gcd(10^n-1, 10^m - 1)=\gcd(10^n-1, (10^m-1)-(10^n-1)) $

$= \gcd(10^n-1, 10^m - 10^n) = $

$\gcd(10^n-1, 10^{\min(n,m)}(10^{\max(n,m)-\min(n,m)} -1))$

which, as $\gcd(10^k, 10^n-1) = 1$ for all $k$, must be equal to $\gcd(10^n-1, 10^v- 1)$ where $v=\max(n,m)-\min(n,m)$.

And that's it, really...

By induction we can replicate Euclid's algorithm to get $k*n + j*m = \gcd(n,m)$ to show that $\gcd(10^n-1, 10^m-1) = 10^{\gcd(n,m)}-1$ and as $\gcd(n,m) = 1$ then $\gcd(10^n -1 , 10^m - 1) = 10^1 - 1 = 9$.

And $\gcd(R_n,R_m) = $

$\gcd(\frac{10^n-1}9, \frac {10^m-1}9) = $

$\frac 19\gcd(10^n-1, 10^m - 1)= 1$.