# How to divide $2x \equiv 4 \pmod {7}$ to get just $x \equiv \Box \pmod{7}$

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$ ?

-
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
@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
@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

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*}

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

-