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?

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.

  • $\begingroup$ 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. $\endgroup$ – Jack Apr 13 '12 at 4:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Apr 13 '12 at 4:16
  • $\begingroup$ Note $\ $ The correct reference is Gauss, Disquisitiones Arithmeticae, Art. 13 (p. 5 of English translation). $\endgroup$ – Key Ideas Jun 3 '13 at 0:18
  • $\begingroup$ (+1) for mentioning Gauss. Well, I'm only centuries late to his party. From what you are writing it appears that my proof of Euclid's lemma is the same argument Gauss used in his Disquisitiones Arithmeticae. $\endgroup$ – CopyPasteIt Feb 26 '20 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.