Finding GCD

Today, I am sharing a little problem from number theory, which is stated as:

Let $a = 7k + 2$ and $b = 9k - 5$. Then, prove that $gcd(a,b)$ is either 1 or 53.


The solution repeatedly makes use of the fact that, if $m > n$, $ gcd(m , n) = gcd(m - n, n) $. It proceeds as follows:

$ \begin{aligned} gcd (a,b) & = gcd(7k+2,9k-5) \\ & = gcd(7k+2,2k-7) \\ & = gcd(5k+9,2k-7) \\ & = gcd(3k+16,2k-7) \\ & = gcd(k+23,2k-7) \\ & = gcd(k+23,-53) \\ & = gcd(k+23,53) \end{aligned} $

Since 53 is a prime number, either it divides $k+23$, in which case we have $gcd(a,b) =$ 53, or it does not divide $k+23$, which makes $gcd(a,b) =$ 1. Hence proved.

The identity $ gcd(m , n) = gcd(m - n, n) $ doesn't just help us solve this particular problem. It is actually the core idea behind Euclid's recursive algorithm for computing the GCD of two integers. The earliest surviving description of the Euclidean algorithm can be found in Euclid's 'Elements' (c. 300 BC), making it one of the oldest numerical algorithms still in common use.