Question

4, Find a number x such that x = 1 mod 4, x 2 mod 7, and x 5 mod 9.

Answer 1

4, 7 and 9 are mutually coprime, so you can use the Chinese remainder theorem.

Start with

$x=7\cdot9+4\cdot2\cdot9+4\cdot7\cdot5$

Taken mod 4, the last two terms vanish and we're left with

$x\equiv63\equiv64-1\equiv-1\equiv3\pmod4$

We have $3^2\equiv9\equiv1\pmod4$, so we can multiply the first term by 3 to guarantee that we end up with 1 mod 4.

$x=7\cdot9\cdot3+4\cdot2\cdot9+4\cdot7\cdot5$

Taken mod 7, the first and last terms vanish and we're left with

$x\equiv72\equiv2\pmod7$

which is what we want, so no adjustments needed here.

$x=7\cdot9\cdot3+4\cdot2\cdot9+4\cdot7\cdot5$

Taken mod 9, the first two terms vanish and we're left with

$x\equiv140\equiv5\pmod9$

so we don't need to make any adjustments here, and we end up with $x=401$.

By the Chinese remainder theorem, we find that any $x$ such that

$x\equiv401\pmod{4\cdot7\cdot9}\implies x\equiv149\pmod{252}$

is a solution to this system, i.e. $x=149+252n$ for any integer $n$, the smallest and positive of which is 149.