HCF of two huge numbers

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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