# Find the smallest positive integer satisfying 3 simultaneous congruences

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

-
thanks everyone, great answers – Arvin Oct 31 '12 at 8:13

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

-

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

-

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

-

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

-