Find when three numbers have the same remainder when divided by the same number

Question

If three numbers 112, 232, and 400 are each divided by the number D, each of their quotients will have the same remainder R. Find R where R>1

How should I approach this?

Answer 1

Hint: $$112 - R \equiv 0 \mod D$$

$$232 - R \equiv 0 \mod D$$

$$400 - R \equiv 0 \mod D$$

$$120 \equiv 0 \mod D$$ $$168 \equiv 0 \mod D$$

Hence $D$ is a common factor of both $120$ and $168$.

$$24 \equiv 0 \mod D$$

$D \in \{1,2,3,4,6,8,12,24 \}$

Use $R>1$ to identify which $D$ is possible.

Answer 2

We have $112 \equiv 232 \equiv 400 \pmod{D}$. This is equivalent to $D$ dividing their pairwise differences: $D \mid 120,168,288$ and so $D \mid 24$. Therefore, $1,2,3,4,6,8,12,24$ are possibilities for $D$ but since $R > 1$ we have only $D = 6,12,24$.

Answer 3

This is the question that when we subtract $x$ from $112, 232,400$, then we should get three numbers commonly divisible by some $D > x$. That is, $D | 112 - x, 232 - x, 400-x$ for $x < D$.

Before we think twice, I've got the answer: $x=16$ , and the numbers are $96,216,384$, commonly divisible by $24 = D$.

Note that the greatest common divisor of the numbers is $8$: $112 = 8*14, 232=8*29, 400=8*50$ . Hence, if $x$ is a multiple of $8$, then it is seen that the numbers $112-x, 232-x, 400-x$ are divisible by $8$ as well. However, if these all are divisible by $8$, so are their differences: $232-112 = 120, 400-232=168, 400-112 = 288$. These numbers, however, are also divisible by $24$. So we take the guess $24$ and it works out. So $R=16, D=24$ works.

Anything else that must work must be a divisor of $24$, as we have seen. We can rule out some of the possibilities:

1) $D=1,2,4,8$ can be ruled out, because on division by these, the remainder zero is left all the time.

2) On division by $3$, they all leave remainder $1$. So here is one answer, but then $R>1$ is given in the question, so this is not considered.

3) On division by $6$ and $12$, they leave the remainder $4$.

4) On division by $24$, they leave the remainder $16$.

The following is a complete description of the problem's answer.

Answer 4

It's solvable by a general method, viz. CRT = Chinese Remainder Theorem. Recall

$$\begin{align} r \equiv a_1\!\!\!\pmod{d_1}\\ r \equiv a_2\!\!\!\pmod{d_2}\\ r \equiv a_3\!\!\!\pmod{d_3} \end{align}$$

is solvable $\!\iff\!$ the congruences are pairwise solvable $\!\iff\!$ $\,\gcd(d_i,d_j)\mid a_i-a_j\,$ for all $\,i\neq j$

We have $\,a_i = 112,232,400\,$ and $\,d_i = d\,$ $\Rightarrow$ $\,\gcd(d_i,d_j)=d,\,$ so the solvability condition is

$$ \begin{align}d\mid 232\!-\!112=120\\ d\mid 400\!-\!232=168\\ d\mid 400\!-\!112=288\end{align}\iff d\mid\gcd(120,168,288)=24\qquad$$

Now we need only check which divisors of $24$ yield remainder $\,r>1,\,$ which is easy.