Solutions to congruence equations

Proposition: Let $n>0$ be an integer, and let $a$ and $b$ be integers. Consider the congruence equation \(ax\equiv b\pmod{n}.\) Finally let $d=\mathrm{gcd}(a,n)$. Then if $d\not|b$, this equation has no solutions. Otherwise, it has $d$ solutions modulo $n$ given by $x=x_0+nk/d$ for $k=0,1,\ldots,d-1$ where $x_0$ is any solution to the congruence.

Proof: First, notice that if $x$ is a solution then by definition we have $n|(ax-b)$ so $ax-b=kn$ for some $k$ and thus $b=ax-kn$. But if $d=\mathrm{gcd}(n,a)$ then $d|n$ and $d|a$ then by this equation also $d|b$. By the contrapositive if $d\not|b$ then no solution $x$ can exist.

We now solve the equation algorithmically.

  • Step 1: Use Euclid’s algorithm to find $u$ and $v$ so that \(au+nv=d.\)

  • Step 2: Find $r$ so that $b=dr$ (if you can’t, there are no solutions). Multiply through by $r$ to obtain: \(aur+nvr=dr=b.\) Notice that this equation tells us that $aur\equiv b\pmod{n}$ so $x=ur$ is a solution to the original congruence.

  • Step 3: Suppose $y$ is another solution to the congruence. Then subtracting the congruences $ax\equiv b\pmod{n}$ and $ay\equiv b\pmod{n}$ we obtain $a(x-y)\equiv 0\pmod{n}$; in other words, $n|a(x-y)$. In other words \(a(x-y) = nz\) for some $z$. Dividing both sides of this equation by $d$ yields \(\frac{a}{d}(x-y) = \frac{n}{d}z.\)

  • Step 4. Dividing the equation in Step 1 by $d$ gives us: \(\frac{a}{d}u+\frac{n}{d}v=1.\) Multiply both sides by $(x-y)$ to yield \(\frac{a}{d}u(x-y)+\frac{n}{d}v(x-y)=x-y.\) Since $n/d$ divides both terms on the left of this equation, it divides $(x-y)$ – in other words, $y=x+k\frac{n}{d}$ for some integer $k$.

  • Step 5: We now know that any solution must be of the form $x+k\frac{n}{d}$, and in fact \(a(x+k\frac{n}{d}) = ax+ak\frac{n}{d} \equiv b+\frac{a}{d}kn\equiv b\pmod{n}\) so these are in fact solutions. We only care about congruence classes mod $n$, so the $d$ values $k=0,\ldots, d-1$ give us the solutions mod $n$.

\newpage

Numerical Example

Solve \(14x\equiv -7\pmod{35}.\)

  1. Use Euclid’s algorithm on $14$ and $35$ to obtain: \((14)(-2)+(35)(1)=7.\) Since $7$ divides $b=-7$ there is a solution.

  2. Multiply through by $-1=b/7$: \((14)(2)+(35)(-1)=-7\) so $(14)(2)\equiv -7\pmod{35}$ and we’ve found one solution, namely $x_0=2$

  3. Since $n/d=5$, the solutions are $2,7,12,17,22,27,32$. As a quick check, $(14)(17)=238\equiv 28\equiv -7\pmod{35}$.