# Find all solutions, if any, to the system of congruences x ≡ 7 (mod 9), x ≡ 4 (mod 12), and x ≡ 16 (mod 21)

Using the Chinese Remainder Theorem:

$$m=9\cdot21\cdot12=2268$$

$$M_1=\frac{2268}{9}=252, \space M_2=\frac{2268}{12}=189, \space M_3=\frac{2268}{21}=108$$

but when trying to find the inverse: $252(y_1) \equiv 1 \pmod 9$, $189(y_2) \equiv 1 \pmod{12}$, and $108(y_3) \equiv 1 \pmod{21}$ have no inverse. But the answer is given as $16+252k$. How is this so?

• What are $M_1,M_2,M_3.y_1,y_2,y_3$?? please write in a bit more detail.... please edit your question so that it would be readable..
– user87543
Commented Mar 20, 2014 at 5:17
• you cannot apply CRT, in CRT, you need to make sure the modular is pairwise coprime Commented Mar 20, 2014 at 5:22
• How would I go about solving this? Commented Mar 20, 2014 at 5:24
• What if the moduli were pairwise coprime but one of the congruences did not have an inverse? Commented Mar 20, 2014 at 5:27

$\begin{eqnarray}&&x\equiv\ \ 7\equiv \color{#c00}{16}\pmod 9\\ &&x\equiv\ \ 4\equiv \color{#c00}{16}\pmod {12}\\ &&x\equiv 16\equiv \color{#c00}{16}\pmod{21}\end{eqnarray}$ $\iff$ $\,9,12,21\mid x\!-\!\color{#c00}{16}$ $\iff$ ${\rm lcm}(9,12,21)\mid x\!-\!\color{#c00}{16}$

Finally $\ {\rm lcm}(9,12,21) = {\rm lcm}(3^{\large\color{#0a0} 2},\,3\cdot 2^{\large \color{#0a0}2},\,3\cdot 7) = 3^{\large\color{#0a0}2}\cdot 2^{\large\color{#0a0}2}\cdot 7 = 252.$

Alternatively, algorithmically, by the third congruence $\ x = 16+21n\,$ for an integer $\,n.\,$ Hence

${\rm mod}\ 12\!:\ 4\equiv x= 16+21n\equiv 4-3n\iff 3n\equiv 0\iff 12\mid 3n\iff 4\mid n\iff\ n = 4k$

${\rm mod}\,\ \ 9\!:\,\ 7 \equiv x = 16+84k\equiv 7+3k\ \iff 3k\equiv 0\iff\,\ 9\mid3k\,\iff 3\mid k\,\iff\, k = 3j$

We've proved $\ x = 16+84(3j) = 16+252j.$

Remark $\$ Note, in particular, that there is no need to split into pairwise coprime moduli as in David's answer. Generally, proceeding as above will yield a simpler method - often much so.

Hint. You have to split the congruences into forms with relatively prime moduli before you can use CRT. So you would have for a start \eqalign{ x&\equiv7\pmod9\cr x&\equiv4\pmod3\cr x&\equiv4\pmod4\cr x&\equiv16\pmod3\cr x&\equiv16\pmod7\ ,\cr} which can be simplified to \eqalign{ x&\equiv7\pmod9\cr x&\equiv1\pmod3\cr x&\equiv1\pmod3\cr x&\equiv0\pmod4\cr x&\equiv2\pmod7\ .\cr} Now the second and third are the same congruence so we don't need to write it twice: \eqalign{ x&\equiv7\pmod9\cr x&\equiv1\pmod3\cr x&\equiv0\pmod4\cr x&\equiv2\pmod7\ .\cr} At this stage the first and second congruences involve moduli, one of which is a factor of the other. Therefore we have a potential contradiction here and we have to check to see whether there actually is a contradiction or not. In fact, \eqalign{ x\equiv7\pmod9\quad &\Rightarrow\quad x=7+9k\cr &\Rightarrow\quad x=1+3(2+3k)\cr &\Rightarrow\quad x\equiv1\pmod3\ ,\cr} so the second congruence is redundant and we have to solve \eqalign{ x&\equiv7\pmod9\cr x&\equiv0\pmod4\cr x&\equiv2\pmod7\ .\cr} This is now a "standard" CRT problem because $9,4,7$ are pairwise coprime, and I will leave it up to you. Note that the modulus in the answer will be $9\times4\times7=252$, not $9\times21\times12$ as you claimed.

Addendum. Bill Dubuque has given a very nice short cut in his answer. However you should still know the general method as there won't always be a short cut like this.

• How did you arrive at those split congruences? Commented Mar 20, 2014 at 5:34
• $x\equiv4\pmod{3\times4}$ is equivalent to $x\equiv4\pmod3$ and $x\equiv4\pmod4$. This is the Chinese Remainder Theorem "used backwards". In general, $x\equiv a\pmod{m_1m_2}$ is equivalent to $x\equiv a\pmod{m_1}$ and $x\equiv a\pmod{m_2}$, as long as $m_1$ and $m_2$ are coprime. Commented Mar 20, 2014 at 5:35
• Why is this so? Can you prove that? Or show me a link? Where can I learn about this? Commented Mar 20, 2014 at 5:38
• Where are you learning about CRT? If you have a textbook it should contain a proof. Or if you Google "proof chinese remainder theorem" you will get a lot of links. Commented Mar 20, 2014 at 5:40
• Discrete Mathematics - Rosen. CRT is proven but an example like this where we must the split the moduli is not shown. This is the first time I've seen something like this. Commented Mar 20, 2014 at 5:43