# how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime?

Given that $$U_n=\underbrace{1\cdots1}_{n\text{ times}}$$ and $n >2$, how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime?

Because $U_m= \frac{10^{m}-1}{9}$ and $U_n= \frac{10^{n}-1}{9}$, follows that $U_{n} > 10 U_{m}$, so there is always a prime between them due to the Bertrand's postulate.

Can I prove it using an other way ?

This is an IMO exercise so I think I don't have to use Bertrand's prostulate ! Or if I use it I have to prove it

Edit 1:

I tried using Lemma

We have

$9U_n=10^n-1$

$9U_m=10^m-1$

$\delta=\gcd(U_m,U_n)$

And we have $\gcd(m,n)=1$

So $\delta=10^{\gcd(m,n)}-1$

Where $\delta=10-1=9$

Finnaly $\gcd(9U_m,9U_n)=9$

Then $\gcd(U_n,U_m)=1$

Is it right ?

• What exactly are you trying to prove? Your proof looks fine as long as you note that since $n$ and $m$ have a prime between them, $n \neq m$ and WLOG $m>n$, so $U_m > 10U_n$ and therefore there is a prime between $U_n$ and $U_m$. Are you looking for a proof without referencing Betrand's or one which explicitly uses the fact that there is a prime between $m$ and $n$? Commented Jun 28, 2015 at 18:01
• @GeorgeV.Williams yes im looking for an other solution :) Commented Jun 28, 2015 at 18:03
• On an IMO, you are allowed to use any theorem as long as you can properly refer to it. So if you want to use Bertrand's postulate, then you use that. If you want to use that if $A^2+B^4=C^n$, then $\gcd(A,B,C) \neq 1$, then you cite this as: This has been proven by Michael Bennet, Jordan Ellenberg, and Nathan Ng in 2009. Commented Jun 28, 2015 at 18:56
• @wythagoras can you see the new edit ? Commented Jun 30, 2015 at 11:37
• It is correct, besides one typo, it should be $\delta=10^{\gcd(m,n)}-1$, the -1 should be outside the exponent. However I wonder how this relates to the question. Commented Jun 30, 2015 at 11:42

Let $q$ be any positive integer, and for $n \ge 0$ set $$U_{n} = \frac{q^{n} -1}{q-1}.$$ You want to prove that for $m, n \ge 0$ $$\tag{gcd's} \gcd(U_{n}, U_{m}) = U_{\gcd(n, m)}.$$
This follows from the elementary fact that $U_{n}$ divided by $U_{m}$, with $m > 0$, leaves as a remainder $U_{r}$, where $r$ is the remainder of the division of $n$ by $m$. If you employ Euclid's algorithm on $U_{n}, U_{m}$, you will get the formula (gcd's).
In fact if $n = m t + r$, with $0 \le r < m$, then $$U_{n} = U_{m} \cdot (q^{n-m} + q^{n - 2m} + \dots + q^{n - tm}) + U_{r}$$