0
$\begingroup$

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

  • 0
    http://en.wikipedia.org/wiki/Modular_multiplicative_inverse - for small numbers you can do trial-and-error, for large numbers the extended Euclidean algorithm2011-11-06

2 Answers 2

3

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

  • 0
    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.2011-11-06
3

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.