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

Question

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.

Answer 1

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

Answer 2

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

Added:

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)$.

Answer 3

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]