How to solve a modular arithmetic equation

Identify the coefficients $a$, $b$, and the modulus $m$ in the equation $ax \equiv b \pmod m$. Calculate the greatest common divisor (GCD) of $a$ and $m$, denoted as $d = \gcd(a, m)$.

1. Verify a solution exists: $d$ must evenly divide $b$. If it does not, there are no solutions. 2. Divide the entire equation, including the modulus, by $d$ to yield $a'x \equiv b' \pmod{m'}$, where $a' = a/d$, $b' = b/d$, and $m' = m/d$. Note that $\gcd(a', m') = 1$. 3. Find the modular multiplicative inverse of $a'$ modulo $m'$, denoted $(a')^{-1}$, using the Extended Euclidean Algorithm. 4. Multiply both sides of the reduced equation by $(a')^{-1}$ to isolate $x$, yielding $x \equiv b'(a')^{-1} \pmod{m'}$. 5. Find all $d$ distinct solutions modulo the original $m$ by computing $x_k = x + k m'$ for integers $k = 0, 1, ..., d-1$.

Substitute the derived values of $x$ back into the original equation $ax \equiv b \pmod m$. Evaluate $ax - b$. The result must be an integer multiple of $m$.

Forgetting to divide the modulus $m$ by the GCD $d$ during the reduction step is the most frequent mistake. Another common error is attempting to find a modular inverse for $a$ modulo $m$ when $\gcd(a, m) eq 1$, which is mathematically undefined.