0
$\begingroup$

Find all numbers $r$ for which the system of congruences \begin{align*} x &\equiv r \pmod{6}, \\ x &\equiv 9 \pmod{20}, \\ x &\equiv 4 \pmod{45} \end{align*}has a solution.


Guess and check won't work, thanks in advance for giving a solution!

$\endgroup$
  • $\begingroup$ let $a = lcm(6,20,45) = 180$ then $x+a \equiv x \bmod 6,20$ and $45$, i.e. it has finitely many solutions in the interval $0 \le x < 180$ and all the others are obtained by adding $180k$ $\endgroup$ – reuns Sep 9 '16 at 4:24
1
$\begingroup$

From the second equation, since $x \equiv 9 \pmod{20}$, we know $x$ is odd. Then $r$ can be one of $1$, $3$, and $5$. From the third equation, $x \equiv 4 \pmod{45}$. We see that $x \equiv 1 \pmod{3}$ (since $x = 45y+4$, for some integer $y$). Then we see that $r$ can only be $1$ (since if $x \equiv 3 \mod{6}$, it will have remainder $0$ when divided by $3$ and if $x \equiv 5 \mod{6}$, it will have remainder $2$ when divided by $3$.

$\endgroup$
1
$\begingroup$

Hint: Prove first that a system of congruences $$\begin{cases}x\equiv r\mod a\\x\equiv s\mod b\end{cases}$$ has a solution if and only if $\; r\equiv s\mod\gcd(a,b).$

$\endgroup$
1
$\begingroup$

By the CRT, the constraint $x\equiv 9\pmod{20}$ is equivalent to the couple of constraints $x\equiv 4\pmod{5}$ and $x\equiv 1\pmod{4}$. In a similar way, the constraint $x\equiv 4\pmod{45}$ is equivalent to the couple of constraints $x\equiv 4\pmod{5}$ and $x\equiv 4\pmod{9}$. The last one implies $x\equiv 1\pmod{3}$ while $x\equiv 1\pmod{4}$ implies $x\equiv 1\pmod{2}$, hence the system has a solution iff $\color{red}{r\equiv 1\pmod{6}}$.

$\endgroup$

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.