Euclid’s Algorithm
Check: Make sure you are fine with very basic number theory.
Definition (greatest common divisor)
Given two integers \(a\) and \(b\), the greatest common divisor (GCD) of \(a\) and \(b\), denoted by \(\gcd(a,b)\), is the largest integer that divides both \(a\) and \(b\).
Euclid’s algorithm (300 BC) which computes the GCD of two positive integers is one of the oldest algorithms still useful today.
The algorithm for computing GCD of \(a\) and \(b\), where \(a>b\):
- To compute \(gcd(a,b)\):
- Let \(r = a\bmod b\);
- if \(r = 0\), then the answer is \(b\).
- else, the answer is \(gcd(b,r)\).
This simple yet ingenious algorithm may not be easy to understand without examples.1 Take the numbers 48 and 18.
\[48 = 2 \times 18 + 12\]As the remainder is not 0, we repeat the process with 18 and 12:
\[18 = 1 \times 12 + 6\]One more time with 12 and 6:
\[12 = 2 \times 6 + 0\]As the remainder is now 0, we can stop. The GCD of 48 and 18 is therefore 6.
Another quick example: what is the GCD of 476 and 272? The answer is 68, as we can see from the following steps:
\[\begin{align*} 476 & = 1 \times 272 + 204 \\ 272 & = 1 \times 204 + 68 \\ 204 & = 3 \times 68 + 0 \end{align*}\]So much for how the algorithm works. But why does it work?
The critical observation is that the GCD of any \(a\) and \(b\), with \(a>b\), is the same as the GCD of \(b\) and the remainder of dividing \(a\) by \(b\). In a concise and more formal way, we can state this as:
\[\begin{align} \forall a,b,r\in \mathbb{Z} \text{ s.t. } a>b, gcd(a,b) = gcd(b,a \bmod b) \label{gcdequal} \end{align}\]Why is \eqref{gcdequal} true?
We will see two proofs of \eqref{gcdequal}, both correct. You decide which one is “better”.
Proof (\eqref{gcdequal}, version 1):
Let’s say \(gcd(a,b)=g\), we want to show that \(gcd(b,r)=g\), where \(r=a \bmod b\). We can think of this task as two sub-tasks: (1) show that \(g\) divides both \(b\) and \(r\), and (2) show that any other common divisor of \(b\) and \(r\) cannot be larger than \(g\).
First part:
- As \(gcd(a,b)=g\), then \(g\) divides both \(a\) and \(b\), and we can write \(a=mg\) and \(b=ng\) for some integers \(m,n\).
- Let \(r=a \bmod b\), which means \(a=kb+r\), and therefore \(r=a-kb\) for some integer \(k\).
- Replace \(a,b\) with \(mg,ng\) respectively in the equation for \(r\) to get \(r=mg-k(ng)=g(m-kn)\).
- As \(m-kn\) is an integer, we can conclude that \(r\) is divisible by \(g\).
- We already know that \(g\mid b\), therefore \(g\) is a common divisor of \(b\) and \(r\).
Second part:
- Assume that there is another common divisor of \(b\) and \(r\), call it \(h\), where \(h > g\).
- First, \(h\nmid a\), because otherwise \(h\) becomes a common divisor of \(a\) and \(b\) larger than their GCD \(g\), which is a contradiction.
- As \(h\) divides both \(b\) and \(r\), we can write \(b=ph\) and \(r=qh\) for some integers \(p,q\).
- Replace \(b\) and \(r\) in the equation \(a=kb+r\) with \(ph\) and \(qh\), respectively. We get \(a=k(ph)+qh=h(kp+q)\), which in turn means \(h\mid a\), given that \(kp+q\) is guaranteed to be an integer. Again we contradicted ourselves.
- Therefore \(b\) and \(r\) cannot have a common divisor larger than \(g\), completing the proof
Here is a slightly different proof. In this we will not proceed over the GCD of \(a\) and \(b\) directly, but prove that the set of common divisors of \(a\) and \(b\) is the same with the set of common divisors of \(b\) and \(r\). As the GCD is defined as the largest common divisor, if the two sets are the same, their GCDs must be the same as well.
Proof (\eqref{gcdequal}, version 2):
Let \(A = \lbrace x: x\mid a, x\mid b \rbrace\) and \(B = \lbrace y: y\mid b, y\mid r \rbrace\) be the sets of common divisors of \(a\) and \(b\), and \(b\) and \(r\), respectively. We want to show that \(A = B\).
First show \(A \subseteq B\):
Pick any \(g\in A\), then by the exact same steps in the earlier proof, you deduce \(g\mid b\) and \(g\mid r\), and therefore \(g\in B\).
Second show \(B \subseteq A\):
Pick any \(h\in B\), then by the exact same steps in the earlier proof, you deduce \(h\mid a\) and \(h\mid b\), and therefore \(h\in A\).
In my opinion, there is an air of elegance in the second proof, in the sense that it does not resort to proof by contradiction.
Having proved \eqref{gcdequal}, we now know that we can reduce the problem of finding GCD of \(a\) and \(b\) to finding GCD of \(b\) and \(r\). To complete the picture for now, we will count on our intuition, without a rigorous proof,2 that repeating this process will eventually lead us to a remainder of 0, at which point the other number is the GCD.