Prove that if $\gcd(n, m) = 1$, then $\gcd(R_n, R_m) = 1$

991 Views Asked by At

We will call a number with $i$ consecutive $1$s in its decimal representation a repunit and denote it by $R_i$.

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

This looked like a proof by contradiction, so I assumed that $\gcd(n, m) = 1$ and $\gcd(R_n, R_m) = d \neq 1$. We are required to find a contradiction.

Now, the above implies that for some integers $a$ and $b$, $da = R_n$, and $db = R_m$. Assume without loss of generality that $R_n \leq R_m$. This means $R_m = R_n\cdot 10^{m-n} + R_{m - n}$

Clearly, $d \mid R_n\cdot 10^{m-n} \implies d\mid R_{m-n}$

Also, $R_{m+n} = R_m\cdot 10^n + R_n = db\cdot 10^n + da = d(10^nb + a) \implies d\mid R_{m+n}$

Even after numerous manipulations of the above results I could not produce a contradiction.

1

There are 1 best solutions below

1
On

HINT:

If $$R_{(n,b)}=\underbrace{(11\cdot11)_b}_{n \text{ digits}}=\frac{b^n-1}{b-1}$$ where base $b$ is a positive integer $>1$

Using this, $$(b^n-1,b^m-1)=b^{(n,m)}-1$$ where $m,n$ are positive integers

$$\implies\left(R_{(n,b)},R_{(m,b)}\right)=R_{((n,m),b)}$$