We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website.
Please click on "Accept cookies" if you agree to the setting of cookies. Cookies that do not require consent remain unaffected by this, see
cookie policy and privacy policy.
DECLINE COOKIES

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.

iamdaone Sep 12, 2018

#1**+7 **

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

\(\begin{array}{|rclll|} \hline x &\equiv& 9 \pmod{20} \\ x &\equiv& 4 \pmod{45} \\ \text{or} \\ x &=& 9 + 20n \quad | \quad n \in Z \\ x &=& 4 + 45m \quad | \quad m \in Z \\\\ && & x = 9 + 20n = 4 + 45m \\\\ && & 20n = 45m - 5 \quad & | \quad : 5 \\\\ && & 4n = 9m - 1 \\\\ && & \mathbf{ n = \dfrac{9m-1}{4} }\\\\ && & n = \dfrac{8m+m-1}{4} \\\\ && & n = 2m+\underbrace{\dfrac{m-1}{4}}_{=a} \\\\ && && a = \dfrac{m-1}{4} \\\\ && && 4a = m-1 \\\\ && & & \mathbf{ m = 4a + 1 } \\\\ && & \mathbf{ n = \dfrac{9(4a + 1 )-1}{4} }\\\\ && & n = 9a + \dfrac{8}{4} \\\\ && & \mathbf{ n = 9a + 2 }\\\\ \mathbf{x} &\mathbf{=}& \mathbf{9 + 20(9a + 2)} \\\\ x & = & 9+180a+40 \\\\ \mathbf{ x } &\mathbf{ = } & \mathbf{49+180a} \quad | \quad n \in Z \\ \hline \end{array} \)

\(\begin{align*} x &\pmod{20}:& &49\pmod{20}+(180a)\pmod{20} \\ && &= 9 + 0 \\ && &= 9\ \checkmark \\\\ x &\pmod{45}:& &49\pmod{45}+(180a)\pmod{45} \\ && &= 4 + 0 \\ && &= 4\ \checkmark \\\\ r &\equiv x \pmod{6}:&&r = 49\pmod{6}+(180a)\pmod{6} \\ && &r = 1 + 0 \\ && & \mathbf{r = 1} \\ \end{align*}\)

heureka Sep 12, 2018

#2**0 **

Why did you re-post your question with "heureka's" solution appended to it? Is it because you don't understand his solution? Or, is the solution very different from your teacher's way of solving it? Or, is it very different from the solution taught in your textbook?

He is the expert in understanding and solving these "Mod" equations. His solutions of these mod equations is the "formal way" of solving them. If you don't understand the formal solution, then you should consult with your teacher and see what he/she has to say. Maybe they know of a simpler method of solving them, such as "trial and error method", or some other such methods.

You may go online to sites such as this one and see the various methods and theorems used in solving such congruences:

**https://www.cs.cmu.edu/~adamchik/21-127/lectures/congruences_print.pdf **

Good luck to you.

Guest Sep 14, 2018