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

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.

• Did you check if the answer is correct? Apr 22 '16 at 15:44
• @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.... 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$.

• I agree. The author only tried to establish a relation with no explanation. Apr 22 '16 at 15:50
• Can you give an example where this formula doesn't work.... Apr 22 '16 at 15:53
• @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 Apr 22 '16 at 15:56
• Can you please explain how to got $7s\equiv 1\pmod8?$ Apr 22 '16 at 16:03
• @tatan Divide everything by $4$. Note you also divide the modulo, as it's divisible by 4. 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)$.
• 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? Jun 9 '16 at 16:17
• @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$. Jun 9 '16 at 16:58