3
$\begingroup$

$x \equiv 2 \pmod 3$
$2x \equiv 4 \pmod 7$
$x \equiv 9 \pmod {11}$

What is troubling me is the $2x$.

I know of an algorithm (not sure what it's called) that would work if all three equations were $x \equiv$ by using euclidean algorithm back substitution three times but since this one has a $2x$ it won't work.

Would it be possible to convert it to $x\equiv$ somehow? Could you divide through by $2$ to get

$x \equiv 2 \pmod{\frac{7}{2}}$

Though even if you could I suspect this wouldn't really help..

What would be the best way to do this?

  • 0
    Since $2$ and $7$ are relatively prime, $\dfrac 12$ exists modulo $7$. In this case, that $\dfrac 12 \equiv 4 \pmod 7$ is irrelevant. We can argue that $2x \equiv 2 \cdot 2 \pmod 7$ and, multiplying both sides by $\dfrac 12$, we end up with $x \equiv 2 \pmod 7$.2017-05-23

5 Answers 5

4

Yes, you can, in a well-defined sense, divide by $2$. The residues modulo a prime form a field; that is, they have multiplicative inverses, in the sense that for each non-zero residue $r$ modulo a prime $p$ there is exactly one residue $s$ modulo $p$ such that $rs\equiv1\bmod p$. In the present case you can find by trial and error that $2\cdot4\equiv1\bmod7$, so you can "divide by $2$" by multiplying by $4$. That yields $x\equiv16\equiv2\bmod7$.

3

If $7$ divides $2x-4=2(x-2)$, then $7$ divides $x-2$, so that the second congruence can be rewritten. Use the Chinese Remainder Theorem to solve.

2

$2$ is invertible modulo $7$. Explicitly we have $4 \equiv 2^{-1} \pmod7$ Multiplying the congruence by $4$ will give you $x\equiv 16 \equiv 2 \pmod7$ You can now use the Chinese Remainder Theorem.

2

Note, that $\mod 7$, $2$ is invertible, as $\operatorname{gcd}(2,7) = 1$. More exactly, we have $1 = 4 \cdot 2 - 7$, that is $1 \equiv 4 \cdot 2 \pmod 7$. Hence $2x \equiv 4 \pmod 7$ holds exactly if (divide by 2, that is, multiply by $2^{-1} = 4$) $x \equiv 16 \equiv 2 \pmod 7$.

1

To supplement the other answers, if your equation was

$ 2x \equiv 4 \pmod 8 $

then the idea you guessed is actually right: this equation is equivalent to

$ x \equiv 2 \pmod 4 $

More generally, the equations

$ a \equiv b \pmod c $

and

$ ad \equiv bd \pmod {cd}$

are equivalent. Thus, if both sides of the equation and the modulus share a common factor, you can cancel it out without losing any solutions or introducing spurious ones. However, this only works with a common factor.