# HCF, LCM, and remainders

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.

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:

1. a(1st term) = 9(7+2) and d(common difference) = 7

2. 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?

-
For small numbers, a solution can usually be easily spotted. For larger numbers, please see (say on Wikipedia) Chinese Remainder Theorem. Part of what is needed is the Extended Euclidean Algorithm, so, as you intuited, the greatest common divisor is involved. – André Nicolas May 25 '12 at 16:57
@AndréNicolas Thanks.The chinese remainder theoren does look like what I want, but actually I am just preparing for a SAT like exam so I guess for small numbers I should stick to my technique. – Kartik Anand May 25 '12 at 17:02
@Kartik Could you please give a more specific example of the precise equations you are attempting to solve. It is not clear from what you wrote. – Bill Dubuque May 25 '12 at 17:04
@BillDubuque for the first part or the second? – Kartik Anand May 25 '12 at 17:07
@BillDubuque I've made the edits – Kartik Anand May 25 '12 at 17:15

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}$

-
Sorry but I guess I don't have the required know how to interpret your answer, actually I am not exactly aware of the symbols you are using(The vertical bar) – Kartik Anand May 25 '12 at 17:00
@KartikAnand the notation $a\,|\,b$ means '$a$ divides $b$'. – Chris Taylor May 25 '12 at 17:05
@ChrisTaylor Silly mistake(I am more comfortable with '/') :) – Kartik Anand May 25 '12 at 17:06
The notation $\rm\:a,b\:|\:c$ means that $\rm\:a\:$ and $\rm\:b\:$ both divide $\rm\:c\,\:$ i.e. $\rm\:c/a,\:c/b\:$ are integers. It is standard number theory notation. One cannot use the notation '/' for that purpose (unless one says $\rm\:c/a\in\mathbb Z$). – Bill Dubuque May 25 '12 at 17:06
@KartikAnand Be sure you understand: $a\,|\,b$ does not mean '$a$ divided by $b$' (that is, $a\div b$), it means '$a$ divides $b$' (that is, $b/a$ is a whole number). – Chris Taylor May 25 '12 at 17:08