10
$\begingroup$

What is the greatest common factor of: $$\underset{m}{\underbrace{111\dots111}}$$ and $$\underset{n}{\underbrace{111\dots111}}.$$ I am guessing that it involves using Euclidean algorithm (matrix-method).

$\endgroup$
4
$\begingroup$

Hint $\ $ The Euclidean algorithm computing their GCD mimics 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\ 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\:$.

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

$ \rm\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.

Remark $\ $ For full proofs and more see the answers to this prior question, which prove

$$\rm \gcd(a^n\! - 1,\, a^m\! - 1)\ =\ a^{\gcd(n, m)}\! - 1 $$

Your result follows by specializing $\rm\ a = 10,\ $ then cancelling $\rm\:a\!-\!1 = 9.$

$\endgroup$
2
$\begingroup$

Hint: Remember that $GCF(a,b)=GCF(a-b,b)$ and $GCF(c,b)=1 \implies GCF(ac,b)=GCF(a,b)$. To be specific, assume $m \gt n$. Think about subtracting $n\ 1$'s from $m\ 1$'s. Then you can divide the difference by $10^n$ to get $GCF(m-n \ 1$'s$,n\ 1$'s$)$. Continue.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.