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.

I've got three simultaneous congruence to solve, which I now know how to do, but in this particular question, one of them is in the form of $2x \equiv$ instead of of $x \equiv$ that I'm used to: $$\begin{align*} x &\equiv 2 \pmod 3\\ 2x &\equiv 4 \pmod 7\\ x &\equiv 9 \pmod{11} \end{align*}$$

How do I divide through the second congruence to get just $x \equiv $ something (mod something) ?

Is it just $x \equiv 2\pmod7$ ?

share|improve this question
    
To get to something more familiar, multiply by the inverse of $2$ modulo $7$. Which is $4$. –  André Nicolas Nov 6 '11 at 4:40
    
Not sure I understand - what do I multiply by 4? –  Arvin Nov 6 '11 at 4:41
2  
@Arvin: Because $4 = \frac{1}{2}\pmod{7}$; that is, $4$ is the number which, when multiplied by $2$, equals $1$ modulo $7$. –  Arturo Magidin Nov 6 '11 at 4:44
1  
@Arvin: The get the $\pmod{a}$ in the question, use the $\LaTeX$ command \pmod{a}. –  Arturo Magidin Nov 6 '11 at 4:44
    
I see, and thanks for the command, I'll use it from now on –  Arvin Nov 6 '11 at 4:54

2 Answers 2

up vote 3 down vote accepted

You divide the usual way; since $\gcd(2,7)=1$, then multiply both sides by $2^{-1}$; since the right hand side is also a multiple of $2$, this is easy: $$\begin{align*} 2x &\equiv 4\pmod{7}\\ 2x &\equiv 2\cdot 2\pmod{7}\\ 2^{-1}2x & \equiv 2^{-1}2\cdot 2\pmod{7}\\ x &\equiv 2 \pmod{7}. \end{align*}$$

If you didn't have it that easy, you can first compute the multiplicative inverse of $2$ modulo $7$: since $2\times 4 \equiv 1 \pmod{7}$, multiply both sides by $4$: $$\begin{align*} 2x &\equiv 4\pmod{7}\\ 8x &\equiv 16\pmod{7}\\ x & \equiv 2 \pmod{7}. \end{align*}$$

share|improve this answer
    
When you see this stuff for the first time, you don't know which way to turn. It's clear that OP didn't have a strategy. One method would have been just to try all the residues modulo 7. This would have worked if the modulus had been 8 instead, when he would have found 6 as another solution. On the other hand, when the modulus is a prime, and so the multiplicative group is cyclic, I like to find a generator and write down all its powers. Modulo 7, you can choose 3 or 5; the powers of 3 are 1, 3, 2, 6, 4, 5, 1,... This makes hand computation of reciprocals and products very easy. –  Lubin Nov 6 '11 at 6:37

You can use the extended Euclidean algorithm to find $n$ and $m$ such that $2n+7m=1$, or in other words $2n\equiv 1\pmod 7$. So $n$ is the multiplicative inverse of $2$ modulo $7$. In this case it turns out that $n=4$ (and $m=1$, but we'll not need that).

Thus, in order to reduce $2x\equiv 4\pmod 7$ just multiply with 2^{-1}=4 on both sides, to get $$8x\equiv 16\pmod 7\qquad\text{which is,}\qquad x\equiv 2\pmod 7$$

A quicker, but less general, way is of course to notice that $4=2\times 2$, and since $\mathbb Z_7$ is an integral domain we're allowed to cancel one of the 2's to get $x\equiv 2\pmod 7$ directly.

share|improve this answer

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.