Consider the linear congruence equation $$ax\equiv b\pmod { n}.$$ One way to solve it is solving a linear Diophantine equation $$ ax+ny=b. $$
I saw somebody solved it by another method somewhere I don't remember:
Solve $144x\equiv 22\pmod { 71}$.
$$\begin{align} 144x\equiv 93 &\pmod { 71}\\ 48x\equiv 31&\pmod { 71}\\ 48x\equiv -40&\pmod { 71}\\ 6x\equiv -5&\pmod { 71}\\ 6x\equiv 66&\pmod { 71}\\ x\equiv 11&\pmod { 71} \end{align} $$
Instead of solving a Diophantine equation using extended Euclidean algorithm, he uses the rules of congruence such as
If $a_1\equiv b_1\pmod {n}$ and $a_2\equiv b_2\pmod {n}$, then $a_1\pm a_2\equiv b_1\pm b_2\pmod {n}$.
Here are my questions:
- Does the second method always work?
- What's the general algorithm for solving $ax\equiv b\pmod {n}$ in this way?