1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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.. $\endgroup$
    – user87543
    Commented Mar 20, 2014 at 5:17
  • 1
    $\begingroup$ you cannot apply CRT, in CRT, you need to make sure the modular is pairwise coprime $\endgroup$
    – delta
    Commented Mar 20, 2014 at 5:22
  • $\begingroup$ How would I go about solving this? $\endgroup$
    – user5826
    Commented Mar 20, 2014 at 5:24
  • $\begingroup$ What if the moduli were pairwise coprime but one of the congruences did not have an inverse? $\endgroup$
    – user5826
    Commented Mar 20, 2014 at 5:27

2 Answers 2

5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ How did you arrive at those split congruences? $\endgroup$
    – user5826
    Commented Mar 20, 2014 at 5:34
  • 1
    $\begingroup$ $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. $\endgroup$
    – David
    Commented Mar 20, 2014 at 5:35
  • $\begingroup$ Why is this so? Can you prove that? Or show me a link? Where can I learn about this? $\endgroup$
    – user5826
    Commented Mar 20, 2014 at 5:38
  • $\begingroup$ 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. $\endgroup$
    – David
    Commented Mar 20, 2014 at 5:40
  • $\begingroup$ 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. $\endgroup$
    – user5826
    Commented Mar 20, 2014 at 5:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .