Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
thanks everyone, great answers –  Arvin Oct 31 '12 at 8:13

5 Answers 5

up vote 4 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.