= Euclidean algorithm
{wiki}
= Euclid’s algorithm
{c}
{synonym}
For positive <integers> $a,b$, the Euclidean algorithm repeatedly performs <division with remainder>: write $a=qb+r$ with $0\leq r<b$, then replace $(a,b)$ by $(b,r)$ until the second entry is zero. The final nonzero entry is their <greatest common divisor>. A remainder preserves the set of common <divisors>: an <integer> divides $a$ and $b$ exactly when it divides $b$ and $a-qb$. The positive remainders strictly decrease, so the calculation terminates.
The complete calculation for $252$ and $198$ is
$$
\begin{aligned}
252&=1\cdot198+54,\\
198&=3\cdot54+36,\\
54&=1\cdot36+18,\\
36&=2\cdot18+0.
\end{aligned}
$$
Hence \b[$\gcd(252,198)=18$]. The <fraction> $252/198$ reduces to $14/11$ by dividing numerator and denominator by that common factor. The same remainder calculation has a geometric interpretation: remove squares from a $252$-by-$198$ <rectangle>, then repeat on the remaining strip. Each division step records how many equal squares fit and the width of the new strip.
\Image[/euclidean-algorithm-rectangles.png]
{title=Successive square removals record the Euclidean algorithm for 252 and 198}
The procedure does more than test individual <divisors>. Each step replaces the whole common-divisor problem by a smaller equivalent one. Euclid's Book VII, Proposition 2 describes the corresponding repeated-subtraction construction; batching those subtractions into <division with remainder> gives the present formulation. https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII2.html[Euclid, Elements VII.2, greatest common measure]{ref}
Back to article page
