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**+1 **

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