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
    To get to something more familiar, multiply by the inverse of $2$ modulo $7$. Which is $4$.2011-11-06
  • 0
    Not sure I understand - what do I multiply by 4?2011-11-06
  • 2
    @Arvin: Because $4 = \frac{1}{2}\pmod{7}$; that is, $4$ is the number which, when multiplied by $2$, equals $1$ modulo $7$.2011-11-06
  • 1
    @Arvin: The get the $\pmod{a}$ in the question, use the $\LaTeX$ command `\pmod{a}`.2011-11-06
  • 0
    I see, and thanks for the command, I'll use it from now on2011-11-06
  • 0
    Multiply both side of the congruence $2x\equiv 4\pmod {7}$ by the inverse of $2$ modulo $7$.2011-11-06
  • 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.