I think this is kind of a lame problem after seeing the quality of questions on this site, but I couldn't find anything related to my question
Now the basic questions is as follows,
Q. Find the least number which when divided by x, y, and z leaves remainder in each case a, b, and c.
A. The solution to this "when x-a = y-a = z-c = D" will be LCM(x, y, z) – D
My 1st question is how is the above possible?
EDIT
For eg. Find the least number which when divided by 3, 4, 5 leaves a remainder of 1, 2, 3 respectively.
Now the answer would be:
D = 3-1 = 4-2 = 5-3 = 2
LCM(3, 4, 5) = 60
So the answer is 60 – 2 = 58
2nd Part
Now the problem comes when x-a <> y-a <> z-a
EDIT
Q. Find the least number when divided by 7 and 5 leaves in each case a remainder 2 , 3 respectively.
The way I thought to solve for numbers 7, 5 leaving a remainder 2, 3 respectively was like this:
Construct two arithmetic sequences:
-
a(1st term) = 9(7+2) and d(common difference) = 7
-
a = 8(5+3) and d = 5
The first term common to these series will be the answer, but shouldn't it be natural that the second question also have an answer that can be deduced by taking LCM, HCF on some operation involving (7, 5) and (2, 3).
But there is also a condition that there will be no solution, the idea is to check till LCM(7,5), why is that?
Best Answer
Hint $\rm\ \ x,y,z\:|\:a\!+\!D \iff m = lcm(x,y,z)\:|\:a\!+\!D.\:$ Thus $\rm\:a\equiv -D\pmod m,\:$ which has least natural representative $\rm\:a = m\!-\!D\:$ if $\rm\:0\le D < m.$
Thus, in your example you have that $\rm\:a\:$ is congruent to a constant value mod all moduli, i.e. $\rm\:a \equiv -D \equiv -2\:\ mod\ 3,4,5,\:$ i.e. $\rm\:3,4,5\:|\:a+2\:$ $\Rightarrow$ $\rm\:60 = lcm(3,4,5)\:|\:a + 2,\:$ therefore $\rm\: a = -2 + 60\:\!k,\:$ with least natural solution $\rm\:a = 58.$
You can find much further discussion of this constant-case of CRT (Chinese Remainder) in many of my prior posts, e.g. here.
The second example isn't a constant case of CRT, but one can use an easy form of CRT, viz.
Theorem (Easy CRT) $\rm\ \ $ If $\rm\ p,\:q\:$ are coprime integers then $\rm\ p^{-1}\ $ exists $\rm\ (mod\ q)\ \ $ and
$\rm\displaystyle\quad\quad\quad\quad\quad \begin{eqnarray}\rm n&\equiv&\rm\ a\:\ (mod\ p) \\ \rm n&\equiv&\rm\ b\:\ (mod\ q)\end{eqnarray} \ \iff\ \ n\ \equiv\ a + p\ \bigg[\frac{b-a}{p}\ mod\ q\:\bigg]\ \ (mod\ p\:\!q)$
Proof $\rm\ (\Leftarrow)\ \ \ mod\ p\!:\:\ n\equiv a + p\ (\cdots)\equiv a\:,\ $ and $\rm\ mod\ q\!:\:\ n\equiv a + (b-a)\ p/p \equiv b\:.$
$\rm\ (\Rightarrow)\ \ $ The solution is unique $\rm\ (mod\ p\!\:q)\ $ since if $\rm\ x',\:x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:p,q\:$ therefore $\rm\ p,\:q\ |\ x'-x\ \Rightarrow\ p\!\:q\ |\ x'-x\ \ $ since $\rm\ \:p,\:q\:$ coprime $\rm\:\Rightarrow\ lcm(p,q) = p\!\:q\:.\quad$ QED
Applying this to your example we find
$\rm\displaystyle\quad\quad\quad\quad\quad \begin{eqnarray}\rm n&\equiv&\rm\ 2\:\ (mod\ 7) \\ \rm n&\equiv&\rm\ 3\:\ (mod\ 5)\end{eqnarray} \ \iff\ \ n\ \equiv\ 2 + 7\ \bigg[\frac{3-2}{7}\ mod\ 5\:\bigg]\ \ (mod\ 7\cdot 5)$
But $\rm\displaystyle\ mod\ 5\!:\ \frac{1}{7} \equiv \frac{6}2\equiv 3,\: $ therefore $\rm\:\ n\:\equiv\: 2 + 7\cdot 3\equiv 23\pmod{7\cdot 5}$