The question is-

Find the smallest number which leaves remainder $8,12$ when divided by $28$ and $32$.

My book gives directly a formula:

Required number $= \mathrm{lcm}(\text{the two numbers; here}\ 28\ \text{and}\ 32) - \text{Sum of their remainders}$

without any proof.

I am not able to derive the proof or find a generalized form of this. I am also wondering what would happen if the numbers remain the same but the remainders are interchanged. Will the same method continue?

Any help is appreciated.

  • $\begingroup$ Did you check if the answer is correct? $\endgroup$
    – N.S.JOHN
    Apr 22 '16 at 15:44
  • $\begingroup$ @N.S.JOHN Yes...$\text{lcm}(28,32)=224$....So,lcm-sum of remainders=$224-20=204$...$204$ divided by $32$ gives $12$ remainder and $204$ divided by $28$ gives $8$ remainder.... $\endgroup$
    – Soham
    Apr 22 '16 at 15:47

This formula isn't true, actually it works just in some cases, yours for example. This is because if $x$ is the required number then working modulo $28$, we have: $x \equiv -20 \pmod{28}$, which coincidentally is equal to $8$ modulo $28$. Try this formula for $22$ and $18$ and respecitve remainders of $5$ and $3$ and you will notice that it doesn't work

To find such a number (which sometimes might not exist) you need to solve the following congurence relations

$$x \equiv 12 \pmod{32} \implies x = 32t + 12$$ $$x \equiv 8 \pmod{28} \implies x = 28s + 8$$

Equating them and solving them you get:

$$32t + 12 = 28s + 8$$ $$28s \equiv 4 \pmod {32}$$ $$7s \equiv 1 \pmod 8 \implies s \equiv 7 \pmod 8 \implies s = 8k + 7$$

Substituting you will get $x = 28(8k + 7) + 8 = 224k + 204$. So the smallest two numbers satisfying the condition are $204$ and $428$.

  • 1
    $\begingroup$ I agree. The author only tried to establish a relation with no explanation. $\endgroup$
    – N.S.JOHN
    Apr 22 '16 at 15:50
  • $\begingroup$ Can you give an example where this formula doesn't work.... $\endgroup$
    – Soham
    Apr 22 '16 at 15:53
  • $\begingroup$ @tatan Read the last sentence of my first paragraph. Your formula gives 190, which gives remainder of 14 and 10, when divided by 22 and 18, respectively, which isn't what we wanted $\endgroup$
    – Stefan4024
    Apr 22 '16 at 15:56
  • $\begingroup$ Can you please explain how to got $7s\equiv 1\pmod8?$ $\endgroup$
    – Soham
    Apr 22 '16 at 16:03
  • $\begingroup$ @tatan Divide everything by $4$. Note you also divide the modulo, as it's divisible by 4. $\endgroup$
    – Stefan4024
    Apr 22 '16 at 16:04

Here is a general way to solve.

It is equivalent to solving the system: $\;\begin{cases}x\equiv8&\bmod 28,\\x\equiv 12&\bmod32.\end{cases}$

There is a formula when the moduli are coprime. We'll reduce the problem to this case.

Any solution has to be divisible by $4$, so we'll set $x=4y$. The congruences can be written as $$\begin{cases}4y\equiv 8\mod 28\\4y\equiv 12\mod 32\end{cases}\iff \begin{cases}y\equiv 2\mod 7\\y\equiv 3\mod 8\end{cases}$$ Now a Bézout's relation between $7$ and $8$ is $8-7=1$, hence the solutions for $y$ are $$y\equiv 2\cdot 8-3\cdot 7=-5\mod 56,$$ whence $\;x=4y\equiv -20\mod 224$. So the smallest positive value is $\;\color{red}{x=204}$.


More generally, one shows a system of linear congruences $$x\equiv a_i\mod m_i\quad(i=1,\dots,r)$$ where the $m_i$ are not necessarily mutually coprime, has a solution if and only if $$\forall i\;\forall j,\enspace a_i\equiv a_j \mod\gcd(m_i,m_j)$$ and in this case, the solution is unique modulo $\operatorname{lcm}(m_1,\dots,m_r)$.

  • $\begingroup$ How do you divide by 4 both sides of the congruence $4y\equiv8\pmod28$?gcd (4,28) is not 1....how did you divide the congruences by 4? $\endgroup$
    – Soham
    Jun 9 '16 at 16:17
  • $\begingroup$ @tatan: I also divided the module. I just simplified by a common factor: $4y\equiv 8 \mod28$ simply means $4y=8+28k$ for some $k$, whence $y=2+7k$, i.e. $\;y\equiv 2\mod7$. $\endgroup$
    – Bernard
    Jun 9 '16 at 16:58
  • $\begingroup$ sorry...I didn't notice the mod change.... $\endgroup$
    – Soham
    Jun 10 '16 at 4:23

The formula given in your book is wrong. I will explain but let me tell about the general types of these questions in detail. The questions are of the form Find the number which when divided by x,y,z ...last divisor leaves the remainders p,q,r...last remainder of corresponding divisor. THESE QUESTIONS ARE ONLY ASKED WHEN x-p= y-q=z-r =...=k (In the given question 28-8=32-12 = 20) . The required number is (LCM OF x,y,z ...) -k The proof of this formula is explained below. Let the required number be L. . L = xa+p = yb+q= zc-r and so on( a, b, c are variables here and are to be written as variables in all questions)(x y z...;p,q,r... will be numbers given in the question) as p = x-k, q = y-k, r = z-k. The above equations can be rewritten as L = xa + x -k= yb +y -k=zc+z -k and so on [L =28a + 28 -20= 32b+32 -20] L= x(a+1) -k=y(b+1)-k=z(c+1) -k and so on [ L=28(a+1)-20=32(b+1)-20] These numbers x(a+1), y(b+1) ,z(c+1) are equal and therefore equal to (m)(LCM OF x, y,z...).(m is any natural number)[LCM =224] L=m( LCM OF x,y,z...)-k [224m -20] and when the smalest value of L is asked m =1[224-20 = 204]


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.