Euclid’s algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers.

Starting with \(k=0\), each step uses two non-negative remainders \(r_{k-2}\) and \(r_{k-1}\) where \(r_{k-2} > r_{k-1}\). The \(k\)th step then provides the quotient \(q_k\) and remaining \(r_k\) where \[ r_{k-2} = q_{k}r_{k-1} + r_{k} \] At the initial step remainders are set to the two inputs so that \(r_{-2}= a\) and \(r_{-1}= b\) allowing the following expansion \[ \begin{align*} a &= q_{0b} + r_0\\ b &= q_{1}r_{0} + r_1\\ r_{0} &= q_{2}r_{1} + r_2\\ r_{1} &= q_{3}r_{2} + r_{3}\\ &\vdots \end{align*} \]

```
GCD(a, b):
WHILE b ≠ 0
t ← b
b ← a mod b
a ← t
RETURN a
```

```
GCD(a, b):
IF b = 0
RETURN a
ELSE
RETURN GCD(b, a mod b)
```