# Question on application of Chinese Remainder Theorem

$$x\; ≡\; 3\; \left( \mbox{mod}\; 30 \right)$$ $$x\; ≡\; 5\; \left( \mbox{mod}\; 56 \right)$$

I have a system of modular equation that I want to solve. However, I thought that this system has no solution because the modulos are not coprime. Further, attempting to solve using chinese remainder theorem:

$$x\; ≡\; 56p\; +\; 30q$$ where $p$ is such that $$56p\; ≡\; 3\; \left( \mbox{mod}\; 30 \right)\;$$ and $q$ is such that $$30q\; ≡\; 5\; \left( \mbox{mod}\; 56 \right)\;$$

However, again the modular inverses of these do not exist.

Yet, one solution to this system of modular inequalities is $1293$. How come the Chinese remainder theorem gives that no solution exists?

-
It doesn't say there is no solution, it isn't applicable (CRT requires relatively prime moduli). Search for "generalized CRT" to get a method to solve such situations (or show they have no solution). It is quite messy, – vonbrand Aug 27 '15 at 0:32

Better if you write it as $$x \equiv 3 \pmod 2,$$ $$x \equiv 3 \pmod {15},$$ $$x \equiv 5 \pmod 8,$$ $$x \equiv 5 \pmod 7.$$

The ones with 2 and 8 are consistent, as the one with 2 is just asking for an odd number, so the system is equivalent to $$x \equiv 3 \pmod {15},$$ $$x \equiv 5 \pmod 8,$$ $$x \equiv 5 \pmod 7,$$ where now the moduli are coprime. That is the requirement for the Chinese Remainder Theorem.

So we combine second and third again to get $$x \equiv 3 \pmod {15},$$ $$x \equiv 5 \pmod {56}.$$

For the 56 one, we have $$5,61,117,173,229,285,341,397,453, \ldots$$ and $$453 \equiv 3 \pmod {15}.$$

-
So you can only solve using the chinese remainder theorem if the modulo are coprime? If they are not coprime (but you know a solution exists) you should try to simplyify the congruences until they become coprime? How do you know whether a solution exists? – 1110101001 Jan 25 '14 at 3:57
@user2612743, I like to actually write out one of the sequences and see when the second condition is also satisfied. I edited in $5 + 56 n,$ eventually got to $453,$ which is also $3 + 15 k.$ – Will Jagy Jan 25 '14 at 3:57
@user2612743, you know a solution exists when you can split it apart, check that the repeated prime power parts (2 and 8 here) are compatible, then shrink the system back down to one with coprime moduli. – Will Jagy Jan 25 '14 at 4:00

The Chinese Remainder Theorem says that a solution exists if and only if $3=5$ modulo the gcd of $30$ and $56$, which is $2$. And, as $5-3=2$...

To solve, you want to write $2=30p+56q$ (from $3+30p=5+56q$, I flipped a sign but that is of no consequence). This is the same as $1=15p+28q$. The general solution to this is $q=7+15k$, $p=-13-28k$, $k\in\mathbb Z$. This gives us $$x=3-30(13+28k),\ \ \mbox{ or }x=5-56(7+15k),\ \ k\in\mathbb Z.$$ For $k=0$ we get $x=-387$. The solution mentioned in the question is $k=-2$, $x=1293$.

-
But how come when trying to solve by taking modular inverse, no modular inverse exists? – 1110101001 Jan 25 '14 at 3:50
I don't really know what you are talking about. See the edit for a way to find the solutions. – Martin Argerami Jan 25 '14 at 4:14
@user2612743 CRT does not apply directly because the moduli have a common factor $2$ that must be cancelled e.g. see my answer. – Bill Dubuque Jan 25 '14 at 4:49

$x = 5\!+\!56j,\ 30\mid x\!-\!3 = 2\!+\!56j\!\overset{\rm cancel\ 2\,}\iff\! 15\mid \color{#c00}1\!+\!\color{#0a0}{28}j \!\overset{\large \begin{eqnarray} \color{#c00}1&\equiv& \color{#c00}{16}\\ \color{#0a0}{28}&\equiv&\color{#0a0}{-2}\end{eqnarray}}\iff\!15\mid \color{#c00}{16}\!\color{#0a0}{-\!2}j=2(8\!-\!j)$ $\!\iff\!$ $15\mid 8\!-\!j$

Hence $\ j= 8\!+\!15n\,$ and $\,x = 5\!+\!56j = 5\!+\!56(8\!+\!15n) = 453 + 840n.$

-