2
$\begingroup$

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).

  • 0
    This is essentially a duplicate of the question linked in my answer.2010-11-16

1 Answers 1

5

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.