Euclid

Euclidean GCD

Use Euclid's algorithm to find a greatest common divisor. This is toy arithmetic only, not deployable security.

cryptography The values in this lesson are deliberately tiny so every modular arithmetic step can be checked exactly.

Example

Use Euclid's algorithm to find a greatest common divisor.

highlighted = computed this step

Step 1 — Set up

Set up the exact toy cryptography values.

a, b(84, 30)\begin{array}{c|c}\text{a, b}&\text{(84, 30)}\end{array}

Step 2 — Euclid row

Compute the highlighted cryptography value.

a, b, q, r(84, 30, 2, 24)\begin{array}{c|c}\text{a, b, q, r}&\hlmath{\text{(84, 30, 2, 24)}}\end{array}

Step 3 — Euclid row

Compute the highlighted cryptography value.

a, b, q, r(30, 24, 1, 6)\begin{array}{c|c}\text{a, b, q, r}&\hlmath{\text{(30, 24, 1, 6)}}\end{array}

Step 4 — Euclid row

Compute the highlighted cryptography value.

a, b, q, r(24, 6, 4, 0)\begin{array}{c|c}\text{a, b, q, r}&\hlmath{\text{(24, 6, 4, 0)}}\end{array}

Final Step — GCD

Compute the highlighted cryptography value.

gcd6\begin{array}{c|c}\text{gcd}&\hlmath{\text{6}}\end{array}