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\notb$, this equation has no solutions. Otherwise, it has $d$ solutions modulo $n$ given by $x=x_0+nk/d$ for $k=0,1,\ldots,d1$ where $x_0$ is any solution to the congruence.
Proof: First, notice that if $x$ is a solution then by definition we have $n(axb)$ so $axb=kn$ for some $k$ and thus $b=axkn$. But if $d=\mathrm{gcd}(n,a)$ then $dn$ and $da$ then by this equation also $db$. By the contrapositive if $d\notb$ 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(xy)\equiv 0\pmod{n}$; in other words, $na(xy)$. In other words \(a(xy) = nz\) for some $z$. Dividing both sides of this equation by $d$ yields \(\frac{a}{d}(xy) = \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 $(xy)$ to yield \(\frac{a}{d}u(xy)+\frac{n}{d}v(xy)=xy.\) Since $n/d$ divides both terms on the left of this equation, it divides $(xy)$ – 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, d1$ give us the solutions mod $n$.
\newpage
Numerical Example
Solve \(14x\equiv 7\pmod{35}.\)

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

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$

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}$.