# gcd(bbb…b, bbb…b)

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

-
This is essentially a duplicate of the question linked in my answer. –  Bill Dubuque Nov 16 '10 at 5:23

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

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

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

and $\rm\ gcd(10,1^{[n]}) = 1\$ since $\rm\ 9\cdot 1^{[n]}\ =\ 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

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

So $\rm\ \ gcd(1^{[m]},1^{[n]})\ =\ gcd(1^{[m-n]}\:,\:1^{[n]})\$ just like $\rm\ gcd(m,n)\ =\ gcd(m-n,n)\:$.

So $\rm\ \ gcd(1^{[m]},1^{[n]})\ =\ 1^{[gcd(m,n)]}\$ follows from the above by a simple induction.

For a full proof and some further insight see my posts in this prior question.

-