TAOCP 4.5.2 Exercise 41

Section 4.5.2: The Greatest Common Divisor

Exercise 41. [M22] Use Euclid's algorithm to find a simple formula for $\gcd(10^m - 1, 10^n - 1)$ when $m$ and $n$ are nonnegative integers.

Verified: yes
Solve time: 23m47s

---

Solution

Let

$$ G(m,n)=\gcd(10^m-1,;10^n-1), $$

where $m,n\ge 0$.

We first treat the case in which one exponent is $0$.

If $n=0$, then

$$ 10^0-1=0, $$

so

$$ G(m,0)=\gcd(10^m-1,0)=10^m-1. $$

Since $\gcd(m,0)=m$, this agrees with the formula

$$ G(m,0)=10^{\gcd(m,0)}-1. $$

Thus it remains to consider the case $n>0$. Assume, without loss of generality, that $m\ge n>0$.

Using Euclid's algorithm,

$$ G(m,n) = \gcd!\bigl(10^m-1,;10^n-1\bigr). $$

Since

$$ 10^m-1 = 10^{m-n}10^n-1 = 10^{m-n}(10^n-1)+(10^{m-n}-1), $$

the remainder upon dividing $10^m-1$ by $10^n-1$ is $10^{m-n}-1$. Hence

$$ G(m,n) = \gcd!\bigl(10^n-1,;10^{m-n}-1\bigr). $$

This is exactly the subtraction step of Euclid's algorithm applied to the exponents $m$ and $n$. Repeating the same argument performs on the pair of exponents precisely the same sequence of reductions as Euclid's algorithm. Therefore, if

$$ d=\gcd(m,n), $$

the process eventually reaches the pair $(d,0)$, giving

$$ G(m,n) = \gcd(10^d-1,;10^0-1) = \gcd(10^d-1,0) = 10^d-1. $$

Thus

$$ \boxed{\gcd(10^m-1,;10^n-1)=10^{\gcd(m,n)}-1}. $$

To justify that this value is indeed the gcd, note that $d=\gcd(m,n)$ divides both $m$ and $n$. Hence

$$ 10^d-1 \mid 10^m-1, \qquad 10^d-1 \mid 10^n-1, $$

because $x^k-1$ divides $x^\ell-1$ whenever $k\mid \ell$.

Conversely, every step above preserves the gcd, so any common divisor of $10^m-1$ and $10^n-1$ must divide the final value $10^d-1$.

Therefore

$$ \boxed{\gcd(10^m-1,;10^n-1)=10^{\gcd(m,n)}-1}. $$

$\square$