3

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!

N. F. Taussig
  • 76,571
Amous
  • 235

1 Answers1

3

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

David
  • 6,306
  • Sorry, I don't quite understand. How did it tell us in advance that there would be a unique solution modulo 154? – Amous Feb 11 '16 at 05:03
  • 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. – David Feb 11 '16 at 05:25