Q:

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

A:

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

