# General method for solving $ax\equiv b\pmod {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?
-

## 1 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.

-
Interesting! Do you have a reference for the Gauss's algorithm you mentioned? I'm also curious about what if the modulus is not prime. –  Jack Apr 13 '12 at 4:02
@Jack Follow the link (and its links) for a precise reference: Gauss: Disq. Arith. Art. 5, 1801. Note that the method may fail if the modulus is not prime. –  Bill Dubuque Apr 13 '12 at 4:16
Note $\$ The correct reference is Gauss, Disquisitiones Arithmeticae, Art. 13 (p. 5 of English translation). –  Key Ideas Jun 3 '13 at 0:18