3
$\begingroup$

The task is to find all integers $x$ such that

$x \equiv 2\pmod 7$

$x \equiv -5\pmod {22}$

My guess is that the Chinese Remainder Theorem may help. I've never done a question like this that had a negative value in one of the equations before. If someone can show me how to solve this that would be great!

$\endgroup$
  • 2
    $\begingroup$ We use a trick. The first congruence can be rewritten as $x\equiv -5\pmod{7}$, so the solution to the system is $x\equiv -5\mod{(7)(22)}$. $\endgroup$ – André Nicolas Feb 11 '16 at 4:52
  • $\begingroup$ @AndréNicolas Very clever! Since I can't vote your comment up, +1! $\endgroup$ – Amous Feb 11 '16 at 5:00
3
$\begingroup$

Using the second equation, write $x = 22t - 5$. Then the first equation becomes $$ \begin{align*} 22t - 5 &\equiv 2 \pmod{7}\\ t &\equiv 0 \pmod{7} \end{align*} $$ Therefore we have $t = 7s$. The general solution is $x = -5 + 154s, s\in \mathbb{Z}$. (We've used the congruences $22 \equiv 1$ and $7 \equiv 0$ modulo $7$. Though we didn't use it here, the Chinese Remainder Theorem actually told us in advance that there would be a unique solution modulo $154$.)

$\endgroup$
  • $\begingroup$ Sorry, I don't quite understand. How did it tell us in advance that there would be a unique solution modulo 154? $\endgroup$ – Amous Feb 11 '16 at 5:03
  • $\begingroup$ When $m$ and $n$ are relatively prime, any system of congruences $x \equiv a \pmod{m}, x \equiv b \pmod{n}$ has a unique solution modulo $mn$. That is exactly what the Chinese Remainder Theorem says. $\endgroup$ – David Feb 11 '16 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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