# Euclidean Algorithm/Least Absolute Remainder

Jump to navigation
Jump to search

## Algorithm

The **Euclidean algorithm** is a method for finding the greatest common divisor (GCD) of two integers $a$ and $b$.

Let $a, b \in \Z$ and $a \ne 0 \lor b \ne 0$.

The steps are:

- $(1): \quad$ Start with $\tuple {a, b}$ such that $\size a \ge \size b$. If $b = 0$ then the task is complete and the GCD is $a$.
- $(2): \quad$ If $b \ne 0$ then you take the least absolute residue $r$ such that:
- $a = q b + r: -\dfrac b 2 < r \le \dfrac b 2$

- $(3): \quad$ Set $a \gets b, b \gets r$ (and thus $\size a \ge \size b$ again).
- $(4): \quad$ Repeat these steps until $b = 0$.

Thus the GCD of $a$ and $b$ is the value of the variable $a$ after the termination of the algorithm.

## Also known as

The **Euclidean algorithm** is also known as **Euclid's algorithm** or the **Euclidean division algorithm**.

## Examples

### Example: $12378$ and $3054$

The GCD of $12378$ and $3054$ is:

- $\gcd \set {12378, 3054} = 6$

and takes $4$ division operations to get there.

## Source of Name

This entry was named for Euclid.

## Sources

- 1980: David M. Burton:
*Elementary Number Theory*(revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm