Finding greatest common factor

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

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

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.