Question on application of Chinese Remainder Theorem

Question

$$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?

Answer 1

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}. $$

Answer 2

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

Answer 3

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