$\gcd(bbb\dots b, bbb\dots b)$

Question

Given the natural numbers $bbb\dots b$ ($n$ digits equal to $b$) and $bbb\dots b$ ($m$ digits equal to $b$), show that the greatest common divisor of these numbers is $bbb\dots b$ ($M$ digits equal to $b$, where $M$ is the greatest common divisor of $n$ and $m$).

Answer 1

Hint $ $ The Euclidean algorithm computing their GCD mimics that for $\rm\: gcd(m,n)\:$.

Put $\rm\ {}^n1\: :=\ 1\cdots 1\ \ (n\ 1's)\ =\ (10^n-1)/9\:.\ $ Then your gcd is $\rm\ b\ gcd({}^m1,\:{}^n1) $

But $\rm\ {}^m1-{}^n1\ =\ {}^{m-n}1\cdot 10^n\ \ \ $ [e.g. $\rm\ 11111 - 111\ =\ 11000\ =\ {}^21\cdot 10^3\ $]

and $\rm\ gcd(10,{}^n1) = 1\ $ since $\rm\ {}^n1\cdot 9 \ =\ 10^n-1\ $ and $\rm\ \rm\ gcd(10,\:10^n-1) = 1\:$.

Hence, choosing notation so that $\rm\:m\ge n\:,\ $ and applying the above observations we have

$\quad\ \ \ \rm gcd({}^m1,{}^n1)\ =\ gcd({}^m1-{}^n1,\:{}^n1)\ =\ gcd({}^{m-n}1\cdot 10^n,\:{}^n1)\ =\ gcd({}^{m-n}1\:,\:{}^n1)$

so $\rm\,\ \ gcd({}^m1,{}^n1)\ =\ gcd({}^{m-n}1\:,\:{}^n1)\ $ just like $\rm\ gcd(m,n)\ =\ gcd(m-n,n)\: $.

so $\,\rm\ \ gcd({}^m1,{}^n1)\ =\ {}^{gcd(m,n)}1\ $ follows from the above by a simple induction.

For a full proof and some further insight see my posts in this prior question, which proves that $$\begin{align} \gcd(10^m-1,10^n-1) &\,=\, 10^{\gcd(m,n)}-1\\[.2em] {\rm i.e.}\ \ \gcd(\, \color{#c00} {}^m1\cdot\color{#c00} 9,\ \ \ \ \color{#c00}{}^n1\cdot\color{#c00} 9 ) &\,=\,\ \ \ {}^{\gcd(n,m)}1\cdot\color{#c00}9\end{align}\qquad$$ so OP follows by cancelling $\,\color{#c00}9\,$ then scaling by $\,\color{#c00}b\,$ (using $\,\gcd(j\color{#c00}c,k\color{#c00}c) = \gcd(j,k)\color{#c00}c\,$ by the gcd distributive law).