Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer
    
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? –  user2612743 Jan 25 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 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 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$.

share|improve this answer
    
But how come when trying to solve by taking modular inverse, no modular inverse exists? –  user2612743 Jan 25 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 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 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.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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