Chinese remainder theorem :Algebraic solution 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?
 A: 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$).
A: 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.
A: 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$.
A: 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$.
A: $$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$
A: Given:
$$x \equiv 8 \pmod{12} \Rightarrow x = 12a + 8 \\
x \equiv 11 \pmod{15} \Rightarrow x = 15b + 11\\
x \equiv 14 \pmod{18} \Rightarrow x = 18c + 14$$
We solve the equations pairwise:
$$1) \ 12a+8=15b+11 \Rightarrow 4a-5b=1 \Rightarrow \begin{cases}a=5n-1 \\ b=4n-1\end{cases}$$
$$2) \ 12a+8=18c+14 \Rightarrow 2a-3c=1 \Rightarrow \begin{cases}a=3m-1 \\ c=2m-1\end{cases}$$
Hence:
$$a=5n-1=3m-1 \Rightarrow a=15k-1.$$
Now we find possible values of $k$:
$$x=12a+8\ge 1000 \Rightarrow 12(15k-1)+8\ge 1000 \Rightarrow k\ge 5.6 \Rightarrow k=6.$$
Hence:
$$a=15\cdot 6-1=89 \Rightarrow x=12\cdot 89+8=1076.$$
