Euclid

Inverse Does Not Exist

Use the gcd to decide when no inverse exists. 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 the gcd to decide when no inverse exists.

highlighted = computed this step

Step 1 — Set up

Set up the exact toy cryptography values.

a, m(6, 21)\begin{array}{c|c}\text{a, m}&\text{(6, 21)}\end{array}

Step 2 — GCD

Compute the highlighted cryptography value.

gcd(a,m)3\begin{array}{c|c}\text{gcd(a,m)}&\hlmath{\text{3}}\end{array}

Step 3 — Verdict

Compute the highlighted cryptography value.

verdictno inverse\begin{array}{c|c}\text{verdict}&\hlmath{\text{no inverse}}\end{array}