For any integer $a,b$ let $N_{a,b}$ denote the number of positive integer $x<1000$ satisfying $x= a \mod 27$ and $x=b \mod 37$. Then which of them is correct

  1. there exist $a,b$ such that $N_{a,b} =0$
  2. for all $a,b$, $N_{a,b}=1$
  3. for all $a,b$, $N_{a,b}>1$
  4. there exist $a,b$ such that $N_{a,b}$ and there exist $a,b$ such that $N_{a,b}=2$.

Since we know that by Chinese Remainder Theorem if $m_1, m_2, .., m_k$ are pairwise relatively prime positive integers, and if $a_1, a_2, .., a_k$ are any integers, then the simultaneous congruences $x ≡ a_1 (mod\;m_1), x ≡ a_2 (mod\;m_2), ..., x ≡ a_k (mod\;m_k)$ have a solution, and the solution is unique modulo $m$, where $m = m_1m_2⋅⋅⋅m_k$. Then how we will approach by acoording to this theorem. So please someone help me and explain it.

  • $\begingroup$ So, calculate $m$ for your problem. And then calculate the number of positive integers $x<1000$. And then think about what's happening. $\endgroup$ – Gerry Myerson Oct 10 '14 at 11:46
  • $\begingroup$ 27 and 37 are pairwise relatively prime so $m=999$ ,$x=a(mod\;999)$ and $x=b(mod\;999)$ then I think $x=999$ is only integer which is divisible by 999 and then we get integer $a=b=0$. Is it right ? @GerryMyerson $\endgroup$ – user114673 Oct 10 '14 at 18:31
  • 1
    $\begingroup$ The Chinese Remainder Theorem says that for every $a$ and every $b$ there is a solution to $x\equiv a\pmod{27}$ and $x\equiv b\pmod{37}$, and what's more this solution is unique modulo 999. "Solution is unique modulo 999" is the same as saying there is exactly one solution among the numbers $1,2,\dots,999$. That should tell you what $N_{a,b}$ is. $\endgroup$ – Gerry Myerson Oct 11 '14 at 3:33
  • $\begingroup$ So, how are we doing? $\endgroup$ – Gerry Myerson Oct 12 '14 at 6:37
  • $\begingroup$ I am not well understand that if we take $a= 2$,$b= 3$ then we are getting the solution $x=299$ and if we take $a=3$, $b=4$ then $x=300$ then how can we say that the solution is unique. $\endgroup$ – user114673 Oct 12 '14 at 12:05

When $n=a (mod\;m_1)$ and $n=b (mod\;m_2)$ are only solvable when $a = b (mod\;(gcd\;(m_1,m_2))$. The solution is unique modulo $lcm\;(m_1,m_2)$. By this we get $a=b\;mod(1)$ which is true for all values of $a$ and $b$. So from here we can say that for all $a,b,\; N_{a,b}=1.$


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.