elementary number theory - General method for solving $axequiv bpmod {n}$ without using extended Euclidean algorithm?

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?

Answer

For this example it is simpler to note that

$$\rm mod\ 71\!:\ \ \frac{22}{144}\: \equiv\: \frac{11}{72}\:\equiv\: \frac{11} 1$$

When the modulus is prime one can employ Gauss's algorithm, for example

$$\rm mod\ 29\!:\ \ \frac{1}8\: \equiv \frac{4}{32}\: \equiv\: \frac{4}{3}\:\equiv\: \frac{40}{30}\: \equiv\: \frac{11}{1}$$

I.e. scale $\rm A/B\ \to AN/BN\ $ by the least $\rm\:N\:$ so that $\rm\ BN > 29\:.\ $ Then reduce the numerator and denominator $\rm\ mod\ 29,\:$ and iterate. You will eventually obtain a denominator of $1$ since each step reduces the denominator. Isn't that sweet? That's they key idea that led Gauss to the first proof of the Fundamental Theorem of Arithmetic, i.e. unique factorization of integers.