Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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