2
$\begingroup$

Using Chinese Remainder Theorem find the remainder of $a$ $\pmod{ 90 }$ given that: $a\equiv 6\pmod {10}$ and $a\equiv 1\pmod 9$

I studied CRT many times but don't get it so as to solve the above simple problem! I don't know how to apply CRT for it...
Please help

$\endgroup$
1
$\begingroup$

$\underbrace{{\rm mod}\,\ \color{#c00}9\!:\ 1 \equiv\! \phantom{a}}_{\large a\ \equiv\ 1\pmod{\! 9}}\!\!\!\!\!\!\overbrace{a\equiv 6\!+\!10k}^{\large a\ \equiv\ 6\pmod{\!10}}\!\!\!\! \equiv -3+k$ $\iff \color{#c00}{k\equiv 4} $ $ \iff a=6+10(\overbrace{\color{#c00}{4+9j}}^{\large\color{#c00} k}) = 46+90j$


Remark $\ $ The same elimination method used above works generally. It leads to a simple form of CRT = Chinese Remainder Theorem that I call Easy CRT. Below is one simple way to present it. You can find many example applications in prior posts here.

Compare the above to the formula below where $\rm {\rm mod}\ 9\!:\, \dfrac{b-a}{m} = \dfrac{1-6}{10}\equiv \color{#c00}{\dfrac{4}1\equiv k}$

Theorem $ $ (Easy CRT) $\rm\ \ $ If $\rm\ m,\:n\:$ are coprime integers then

$$\rm \begin{eqnarray}\rm x&\equiv&\rm a\,\ (mod\ m) \\ \rm x&\equiv&\rm b\,\ (mod\ n)\end{eqnarray} \ \iff\ \ x\, \equiv\, a + m\ \bigg[\frac{b-a}{\color{#c00}m}\ mod\ n\:\bigg]\ \ (mod\ m\:n)$$

Proof $\rm\,\ m,n\,$ coprime $\:\rm\Rightarrow\, \color{#c00}{{\large\frac{1}m} = m^{-1}}\!\pmod n\, $ exists, by Bezout or Euler's $\phi$ Theorem.

$\rm\ (\Leftarrow)\ \ \ mod\ m:\,\ x \equiv a + m\left[\cdots\right] \equiv a,\ $ and $\rm\ mod\ n\!\!:\ x \equiv a + m\,\color{#c00}{\large\frac{1}m}\,(b-a) \equiv b$

$\rm (\Rightarrow)\ \ $ The solution is unique $\rm\, (mod\ m\,n)\, $ since if $\rm\ x',\,x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ hence $\rm\ m,n\mid x'-x\ \Rightarrow\ m\,n\mid x'-x\ $ since $\rm\ m,\,n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = m\,n$.

$\endgroup$
  • $\begingroup$ Thank you so much for your kind and clever guides and answers :) $\endgroup$ – Hamid Reza Ebrahimi Jan 28 '17 at 5:19
1
$\begingroup$

The first congruence says $a=6+10k$ for some $k$. Put it in the second congruence to get $6+10k \equiv 1 (\bmod{9}).$ Solve for $k$. Plug in for $a$. You should get $46$.

$\endgroup$
  • $\begingroup$ But how to solve the equation you mentioned?! $\endgroup$ – Hamid Reza Ebrahimi Jan 27 '17 at 22:31
  • $\begingroup$ So your real problem is that you are working in Chapter 3 without having mastered Chapter 2..... $\endgroup$ – B. Goddard Jan 27 '17 at 22:35
  • 1
    $\begingroup$ @Hamid mod $9$ we have $\color{#0a0}{10\equiv{\bf 1}}\,$ so $\,1\equiv 6+\color{#0a0}{10k}\equiv 6+\color{#0a0}k\,$ so $\,k\equiv 1-6\equiv -5\equiv \color{#c00}4,\,$ same as in my answer. $\endgroup$ – Bill Dubuque Jan 28 '17 at 0:18
1
$\begingroup$

To apply the CRT in a generalisable way we need to find:

$x\equiv 1 \bmod 9;\equiv 0\bmod 10$ which is easy as $x=10$ will do.

$y\equiv 0\bmod 9; \equiv 1\bmod 10$ and $y=81$ will do (or $y=-9$)

Now notice that if we take $px+qy$ modulo $9$ we get $x$, and modulo $10$ we get $y$.

So the answer would be $1\times 10+6\times 81\bmod 90$ which comes out at $46$.

$\endgroup$
1
$\begingroup$

The solution follows from Bézout's identity, from which results an explicit formula for the inverse isomorphism in the Chinese remainder theorem: \begin{align} \varphi\colon\mathbf Z/mn\mathbf Z&\longrightarrow \mathbf Z/m\mathbf Z\times\mathbf Z/n\mathbf Z, \\ x\bmod mn&\longmapsto(x\bmod m,x\bmod n). \end{align} for $m,n$ coprime. If $um + vn=1$ is a Bézout's relation between $m$ and $n$, this inverse isomorphism is given by \begin{align} \varphi^{-1}\colon \mathbf Z/m\mathbf Z\times\mathbf Z/n\mathbf Z&\longrightarrow \mathbf Z/mn\mathbf Z,\\ (x\bmod m,y\bmod n)&\longmapsto yum+xvn\bmod mn. \end{align}

$\endgroup$
1
$\begingroup$

Not a direct answer to your question. there is an easier solution if we can observe the following.

$a\equiv 6\equiv 46\pmod {10}$

The above step was written after going through the numbers $6,16,26,36,46$ because $46$ can be expressed as $9k +1$ (where k is an integer) and therefore, the next expression can be also made in the same format as provided below.

$a\equiv 1\equiv 46\pmod {9}$

Hence, $a\equiv 46\pmod {LCM(10,9)}$

$a\equiv 46\pmod {90}$

$\endgroup$
  • $\begingroup$ For this to be useful you should say how you found the solution $46$. Otherwise it looks as if it was pulled out of a hat - like magic. $\endgroup$ – Bill Dubuque Jan 27 '17 at 23:24
  • $\begingroup$ in this case, i went through numbers of the form $1+9m$ and $6+10n$ and it was easy to find. $\endgroup$ – Kiran Jan 27 '17 at 23:28
  • $\begingroup$ Yes, I figured that, but you should explain that to your readers in the answer, i.e. show the steps that you took, the specific numbers tested, etc. $\endgroup$ – Bill Dubuque Jan 27 '17 at 23:42
  • $\begingroup$ @BillDubuque, please see my edit. $\endgroup$ – Kiran Jan 27 '17 at 23:50
  • $\begingroup$ That's clearer. Such brute-force checking of all possible values is often useful when computing with small moduli. But I would not recommend that one use such methods when one seeks to learn how to do CRT in general, since brute-force checking will be impractical except for very small moduli. $\endgroup$ – Bill Dubuque Jan 28 '17 at 0:14

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.