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

  • $\begingroup$ 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, $\endgroup$ – 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}. $$

  • $\begingroup$ 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? $\endgroup$ – 1110101001 Jan 25 '14 at 3:57
  • $\begingroup$ @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.$ $\endgroup$ – Will Jagy Jan 25 '14 at 3:57
  • $\begingroup$ @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. $\endgroup$ – 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$.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.