Euclid

Euclidean GCD

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

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}
cryptography The values in this lesson are deliberately tiny so every modular arithmetic step can be checked exactly.