Solve for $x$ the following congruence system

98 Views Asked by At

I will first let you know the problem, then I will tell you what I tried : I have to solve the congruence system,

$20x \equiv{9} \mod{30}$

$9x \equiv{12} \mod{33}$

$36x \equiv{49} \mod{60}$

With the Chinese remainder theorem, I tried to replace the equations because $30$, $33$ and $60$ have commons factors. I found prime decomposition for all modulo $30$, $33$ and $60$ and replaced those prime factor as new modulars. By simplifying I found :

$2x \equiv{0} \mod{4}$

$x \equiv{3} \mod{5}$

$9x \equiv{1} \mod{11}$

I found $x=1728$ for the new system but it does not match with the first system. Maybe there is no solution?

1

There are 1 best solutions below

0
On BEST ANSWER

The first system of equations can have no solution. You require $36x\equiv49\mod60$. In other words, you need $36x=60k+49$, or $36x-60k=6(6x-10k)=49$, or $6x-10k=\frac{49}{6}$. But this is impossible! Assuming $x,k\in\mathbb{Z}^1$, $6x-10k\in\mathbb{Z}$, but $\frac{49}{6}=8\frac{1}{6}\not\in\mathbb{Z}$, which is a contradiction. Thus your original system of equations has no solution.

$^1$I know you didn't explicitly $\textit{say}$ that $x$ was an integer, but it's a sufficiently common assumption in these problems I felt comfortable assuming it.

Also, you have a similar problem with $20x\equiv9\mod30$. You can reach the same conclusion by rereading the first paragraph of my solution with $36\to20,49\to9,60\to30$.