Chinese remainder theorem :Algebraic solution

Question

I need help in a question:

It is required to find the smallest $4$-digit number that when divided by $12,15$, and $18$ leaves remainders $8,11$, and $14$ respectively. Here's how I've attempted:

Let the number be $a$, then $$a=12p+8 = 15q+11 = 18r+14$$ Hence, $p=(5q+1)/2$ and $r=(5q-1)/6$

So, $a=15q+11$

Now if I put $q=67$, $a=1016$ (wrong answer because $r$ is not an integer) .

So where did I go wrong in the algebraic method?

Answer 1

Your algebraic method is correct, but to get the right solution you cannot choose $q$ arbitrarily. $p=(5q+1)/4, r=(5q-1)/6$ give you additional restrictions for $q$ namely that $5q+1$ be divisible by $4$ and that $5q-1$ be divisible by $6$. So you just need to choose $q$ minimal such that $15q+11$ has four digits and $4|5q+1, 6|5q-1$. The right answer should be $q=71, a=1076$.

Answer 2

We have:

$$x \equiv 8 \pmod{12} \implies x = 12a + 8$$ $$x \equiv 11 \pmod{15} \implies x = 15b + 11$$ $$x \equiv 14 \pmod{18} \implies x = 18b + 14$$

From these relation we continue:

$$x = 12a + 8 = 15b + 11$$ $$12a = 15b + 3$$ $$4a = 5b + 1$$ $$4a \equiv 1 \equiv 16 \pmod 5$$ $$a \equiv 4 \pmod 5 \implies a = 5d+4$$

Now we make a substitution:

$$x = 12a + 8 = 12(5d + 4) + 8 = 60d + 56$$

$$60d + 56 = 18c + 14$$ $$60d + 42 = 18c$$ $$10d + 7 = 3c$$ $$10d + 7 \equiv 0 \pmod 3$$ $$d \equiv 2 \pmod 3 \implies d=3n + 2$$

Now we substitute once again.

$$x = 60(3n + 2) + 56 = 180n + 176$$

So all solution are of the form $180n + 176 \forall n \in \mathbb{N}$

For $n=5$ we get the smallest 4-digit solution, which is 1076.

Answer 3

So, we know that

$12p + 8 = 15q + 11$, and therefore,
$12p = 15q + 3 \Rightarrow 4p = 5q + 1 \Rightarrow p = \frac{5q+1}{4}$, so there's the first problem.

The second problem: Any solution to those set of equations has to be the same mod $lcm(12,15,18) = 180$. Hence, over all of the solutions, $q$ would have to be the same mod 12.

Testing out small values, $q = 11$ yields $p = 14, r = 9, a = 176$. Since $11 \neq 67$ mod $12$, $67$ just isn't one of the possible values for $q$ in the set of solutions; the correct value for $q$ must be congruent to 11. As mentioned in the other answers, the correct value for $q$ is 71 (yielding $1076$).

Answer 4

Here's a quick way that's unique to the values in this problem.

Let the answer be $N$. Show that $N+4$ is a multiple of 12, 15 and 18, hence is a multiple of their LCM which is 180.

Thus the smallest 4-digit number is $10 \times 180 - 4 = 1076$.

Answer 5

$$a = 12p+8 = 15q+11 = 18r+14$$

You should break these down into linear expressions with prime-power coefficients.

$$a = 12p+8 \implies a = \left\{ \begin{array}{c} 4(3p+2) \\ 3(4p+2)+2 \end{array} \right \}$$

$$a = 15q+11 \implies a = \left\{ \begin{array}{c} 3(5q+3)+2 \\ 5(3q+2)+1 \end{array} \right \}$$

$$a = 18r+14 \implies a = \left\{ \begin{array}{c} 2(9r+7) \\ 9(2r+1)+5 \end{array} \right \}$$

---

Some of these can be combined.

$$a = \left\{ \begin{array}{c} 4(3p+2) \\ 2(9r+7) \end{array} \right \} \implies a = 4u$$

$$a = \left\{ \begin{array}{c} 3(4p+2)+2 \\ 3(5q+3)+2 \\ 9(2r+1)+5 \end{array} \right \} \implies a = 9v+5$$

$$a=5(3q+2)+1 \implies a = 5w+1$

---

$$\left\{ \begin{array}{l} a=4u \\ a=9v+5 \\ a=5w+1 \end{array} \right \} \implies \left\{ \begin{array}{l} 45a=180u \\ 20a=180v+100 \\ 36a=180w+36 \end{array} \right \} \implies \left\{ \begin{array}{rcl} 45a &=& 180u \\ -80a &=& 180(-4v)-400 \\ 36a &=& 180w+36 \end{array} \right \} $$

Adding the three equations, we get

$$ n= 180x + 176$$

Since the smallest $3$-digit number is $100$, the smallest $3$-digit number of the form $ n= 180x + 176$ must be between $100$ and $100+180-1=279$

\begin{array}{c} 100 &\le &180x+176 &\le &279 \\ -76 &\le &180x &\le &103 \\ -\dfrac{76}{180} &\le &180x &\le &\dfrac{103}{180} \\ 0 &\le &180x &\lt &1 \\ &&x &= &0 \end{array}

So $n=176$