Finding the smallest $x$ given a set of congruence conditions.

Question

Find the smallest integer $x$ such that

$$x \mod 5 = 3\\ x \mod 7 = 4\\ x \mod 9 = 6$$

Can you tell me how to solve this type of question? I don't need a solution.

---

Clearly the smallest $x$ for the first one is $8$. The smallest $x$ for the second one is $11$. And for the last one it is $12$. Since $12$ is the highest of the three solutions, the $x$ I am looking for must be greater than or equal to $12$. However, $12 \mod 7 = 5 \not = 4$, so $x$ cannot be $12$ as it does not fulfil the second condition.

Technically, I can keep on going up and up until I find a fitting number for the three conditions, but I doubt that's how I am supposed to do this.

Answer 1

A simple approach, which may help motivate the Chinese Remainder Theorem. Start with $x=3$, which satisfies the first equation. We can add as many $5$'s to it as we want without spoiling the first equation. Now look at the second. We need $x=3+5k\equiv 4 \pmod 7$ For small numbers like this, you can just think $3,8,13,18$ and notice that $18 \equiv 4 \pmod 7$ Now we not to spoil $\pmod 5$ and $\pmod 7$, so we have to add multiples of $35$. We need $18 + 35 m \equiv 6 \pmod 9$ Since the right is a multiple of $3$, so must the left be, so $m$ must be a multiple of $3$ an we need $18+105n \equiv 6 \pmod 9$. $n=1$ works and our answer is $133$. The solutions will recur (though we weren't asked for this) at $5 \cdot 7 \cdot 9=315$

Answer 2

The trick is to make factors that "disappear" modulo the other numbers. So, one answer will be the following:

$$ x = 3 \cdot (7\times 9)(7 \times 9)^{-1}_5 + 4 \cdot (5\times 9)(5 \times 9)^{-1}_7 + 6 \cdot (5\times 7)(5 \times 7)^{-1}_9 $$ Here, $(y)_m^{-1}$ denotes the inverse of $y$ mod $m$. So, for example, $7\times 9 = 63 \equiv 3 \pmod{5}$, and $3 \times 2 \equiv 1 \pmod{5}$, so $(7 \times 9)^{-1}_5 = 2$.

The solution to this problem is unique modulo $5 \times 7 \times 9$.

Answer 3

Apply the Chinese Remainder Theorem: find $b_1$, $b_2$ and $b_3$ such that $$ \begin{matrix} 7\cdot 9b_1 = 1 \pmod{5} \\ 5\cdot 9b_2 = 1 \pmod{7} \\ 5\cdot 7b_3 = 1 \pmod{9} \end{matrix} $$

Then, $$ 3\cdot 7\cdot 9b_1+4\cdot 5\cdot 9b_2+6\cdot 5\cdot 7b_3 \pmod{5\cdot7\cdot9} $$ is the solution.