Solution congruence system $ x \equiv 11\pmod{36},\,x \equiv 7\pmod{40}, \,x \equiv 32\pmod{75}$

Question

Have solution the following congruence system? $$\begin{align} x & \equiv 11\pmod{36}\\ x & \equiv 7\pmod{40}\\ x & \equiv 32\pmod{75} \end{align}$$

Point of Interest: This question requires some special handling due to the mixture of factors among the moduli. This is more than the run of the mill Chinese Remainder Theorem problem.

Answer 1

Hint: It might be easier to break things down into unique and shared factors: $$ \begin{align} x&\equiv7\pmod{8}\\ x&\equiv2\pmod{9}\\ x&\equiv7\pmod{25} \end{align} $$ Once you have it in this form, you can then use the Extended Euclidean Algorithm to solve $$ \begin{align} a&\equiv1\pmod{8}\\ a&\equiv0\pmod{9\cdot25}\\ \end{align} $$ $$ \begin{align} b&\equiv1\pmod{9}\\ b&\equiv0\pmod{8\cdot25}\\ \end{align} $$ $$ \begin{align} c&\equiv1\pmod{25}\\ c&\equiv0\pmod{8\cdot9}\\ \end{align} $$ and get $$ x\equiv7a+2b+7c\pmod{8\cdot9\cdot25} $$

Answer 2

First, break down the individual congruences into coprime factors to see if the system is consistent. So we have

$$x\equiv2\pmod9,x\equiv3\pmod4$$ $$x\equiv7\pmod8,x\equiv2\pmod5$$ $$x\equiv2\pmod3,x\equiv7\pmod{25}$$

Checking the powers of $2$, if $x\equiv2\pmod 9$, then $x\equiv2\pmod3$, so these $2$ equivalences are consistent and we can ignore the second equivalence. If we meet the first of these $2$ conditions, we are guaranteed to meet the second, so the second is redundant.

Doing the same with powers of $3$ and $5$ verifies this system is consistent and reduces the system to

$$x\equiv2\pmod9,x\equiv7\pmod8,x\equiv7\pmod{25}$$

These are actually some good numbers to work with and it might be easier than it looks. If $x-7$ is a multiple of $8$ and $25$, it's a multiple of $200$, so the last $2$ conditions combine to $x\equiv7\pmod{200}$. Now, for a number to be equivalent to $2\pmod9$, the sum of its digits must also be equivalent to $2\pmod9$. Since $x\equiv7\pmod{200}$, its last digit must be a $7$. Using this information, it's not hard to find a number that meets both conditions: $407$. So the solution is $x\equiv407\pmod{1800}$

Answer 3

For comparison, here is pairwise CRT iterated. All arithmetic can be done mentally.

${\rm mod}\ 40\!:\ \ 7\equiv\! \overbrace{x \equiv 32\!+\!75\,\color{#c00}i}^{\large x\,\equiv\, 32\pmod{\!75}}\!\!\equiv 32\!-\!5i\iff 5i=25\!+\!40j\iff \color{#c00}{i = 5\!+\!8j}$

${\rm mod}\ 36\!:\ 11\equiv x\equiv 32\!+\!75(\color{#c00}{5\!+\!8\,\color{#0a0}j})\equiv -4\!+\!3(5\!+\!8\color{}{j})\equiv 11\!+\!24j\iff 36\mid 24j\iff \color{#0a0}{3\mid j}$

So $\,\color{#0a0}{j=3k},\ $ so $\ x = 32\!+\!75(5\!+\!8(\color{#0a0}{3k})) = 407 + 1800k$