0
$\begingroup$

The question asks to find the smallest integer greater than $23$ that leaves the remainders $2,3,2$ when divided by $3,5,7$ respectively. The answer is given as $128$.

I used C.R.T. to solve this. $$x\equiv2\pmod 3\\ x\equiv3\pmod 5\\ x\equiv2\pmod 7 $$ where $M=m_1·m_2·m_3=3×5×7=105$.

From here I get solutions, $$x\equiv2\pmod 3\\ x\equiv1\pmod 5\\ x\equiv1\pmod 7$$
After that I find\begin{align*} x &\equiv 2×2×5×7+1×3×3×7+1×2×3×5\\ &\equiv 140+63+30\\ &\equiv 233 \pmod{105}, \end{align*} where I again find that $x=23$.

But one thing I have noticed that $233=105×1+128$. I cannot continue from here. I need help and any help is highly appreciated.

$\endgroup$
  • 1
    $\begingroup$ The "From here I get solutions..." is incomprehensible for me: how applying the CRT gives you those "solutions" and not the final one, which is unique modulo $\;3\cdot5\cdot7=105\;$ ? $\endgroup$ – DonAntonio Mar 12 '18 at 8:34
  • 1
    $\begingroup$ @thevbm The solutions are actually given by $23+105n$. Since substituting in $n=0$ gives $23$, you can substitute the next $n$ which is $n=1$. $\endgroup$ – Toby Mak Mar 12 '18 at 8:35
  • $\begingroup$ You could just observe that $23$ itself has the correct remainders modulo $3,5$ and $7$. By CRT the solutions form a single residue class modulo $3\cdot5\cdot7=105$, and you already know which class it is! So....? $\endgroup$ – Jyrki Lahtonen Mar 12 '18 at 8:35
1
$\begingroup$

Applying directly the following proof of CRT, for example:

$$\begin{cases}y_1=\frac{105}3=35\;\implies y_1=2\pmod3\implies y_1^{-1}=2\pmod3\\{}\\y_2=\frac{105}5=21\implies y_2=1\pmod5\implies y_2^{-1}=1\pmod5\;\\{}\\y_3=\frac{105}7=15\implies y_3=1\pmod7\implies y_3^{-1}=1\pmod7\end{cases}$$

so that

$$2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1=233\;\;\text{ is a solution, and}$$

$$233=128\pmod{105}\;\;\text{is another solution, and}$$

$$128=23\pmod105\;\;\text{ is the unique solution modulo}\;105$$

Observe that unless you consider things modulo $\;3\cdot5\cdot7=105\;$ at the end , there is not "the" solution, but only one out of infinitely many

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, now I understand and thank you for providing the link. $\endgroup$ – vbm Mar 12 '18 at 9:03
  • $\begingroup$ Following the link you provided, one question I have (from an example given there) to make my doubt clear. suppose system of congruences is given as $x\equiv 5 \mod 6$ $x\equiv 3 \mod 8$. Here g..c.d of the moduli is $2$. The first congruence implies $x\equiv 1\mod 2$, also the second congruence implies $x\equiv 1\mod 2$Now to reduce the system of congruency to a simpler form if we divide the g.c.d of the moduli from the modulud of the first congruence, then how is it $x\equiv2 \mod3$? rather it should be $x\equiv 1 \mod 3$. If I'm wrong, please correct me. Thank you $\endgroup$ – vbm Mar 12 '18 at 9:38
  • 1
    $\begingroup$ @thevbm I'm not sure what your doubt exactly is, but remember the CRT applies for coprime moduli, so reducing your moduli as you did can help...but then you should be careful when going back to the original ones. $\endgroup$ – DonAntonio Mar 12 '18 at 11:53
1
$\begingroup$

Let $x\equiv y \equiv 2 \mod 3,$ and $x\equiv y \equiv 3 \mod 5,$ and $x\equiv y \equiv 2 \mod 7.$ Then $x-y \equiv 0$ modulo $3,5,$ and $7.$

So $x-y$ is divisible by $3,5,$ and $7,$ so $x-y$ is divisible by $(3)(5)(7)=105.$ So if $y=23$ and $x>y$ then $x=23+105n$ for some $n\in \Bbb N.$

And if $x=23+105n$ for some $n\in \Bbb N$ then $x\equiv 23$ modulo $3,5, $ and $7.$

| cite | improve this answer | |
$\endgroup$

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.