HCF of two huge numbers A question goes like :
Find the HCF of $\underbrace{111\ldots 11}_{100\text{ ones}}$ and $\underbrace{111\ldots11}_{60 \text{ ones}}$.
The answer is $\underbrace{111\ldots11}_{20 \text{ ones}}$
I'd like to know how this question is solved along with the logic behind the steps.
All help is appreciated
Cheers!
 A: 3 steps of Euclid's algorithm will get you there:
$$\begin{align} & \gcd(\underbrace{11\cdots11}_{100},\underbrace{11\cdots11}_{60})
\\ ={}& \gcd(\underbrace{11\cdots11}_{40},\underbrace{11\cdots11}_{60}) 
\\ ={}& \gcd(\underbrace{11\cdots11}_{40},\underbrace{11\cdots11}_{20})
\\ ={}& \gcd(\underbrace{11\cdots11}_{20},\underbrace{11\cdots11}_{20})
 = \underbrace{11\cdots11}_{20} \end{align} $$
First subtract $10^{40}$ times the right number from the left, then $10^{20}$ times the left number from the right, then $10^{20}$ times the right number from the left again.
This example generalizes to seeing that
$$ \gcd(\underbrace{11\cdots11}_{a\text{ ones}},\underbrace{11\cdots11}_{b\text{ ones}}) = \underbrace{11\cdots11}_{\gcd(a,b)\text{ ones}} $$
A: Suppose $d$ is the gcd. For ease of notation, let's have $a(n)=$a number with $n$ $1$'s. So $d|a(60)$ and $d|a(100)$.
But $a(100)=a(60)+a(40)\times10^{60}$, and $d|a(60)$ so $d|a(40)\times10^{60}$. But $gcd(d,10)=1$ as neither $a(60)$ nor $a(100)$ have $2$ or $5$ as a prime factor.
So $d|a(40)$. We also have $d|a(60)$ hence $d|(a(60)-a(40))=a(20)\times10^{40}$. Using $gcd(d,10)=1$ we have $d|a(20)$. But $a(20)|a(60)$ and $a(20)|a(100)$ so $a(20)$ is a common factor of both $a(60)$ and $a(100)$ so $a(20)|d$.
These implications yield $d=a(20)$.
A: For integer base $\displaystyle b(\ne1),\underbrace{111...11}_{n\text{ ones}}=\sum_{r=0}^{n-1}b^r=\dfrac{b^n-1}{b-1}$
Using Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$, 
$\displaystyle(b^n-1,b^m-1)=b^{(n,m)}-1$
$\displaystyle\implies\left(\dfrac{b^n-1}{b-1},\dfrac{b^m-1}{b-1}\right)=\dfrac{b^{(n,m)}-1}{b-1}$
