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

Accepted Solution

4, 7 and 9 are mutually coprime, so you can use the Chinese remainder theorem.Start with[tex]x=7\cdot9+4\cdot2\cdot9+4\cdot7\cdot5[/tex]Taken mod 4, the last two terms vanish and we're left with[tex]x\equiv63\equiv64-1\equiv-1\equiv3\pmod4[/tex]We have [tex]3^2\equiv9\equiv1\pmod4[/tex], so we can multiply the first term by 3 to guarantee that we end up with 1 mod 4.[tex]x=7\cdot9\cdot3+4\cdot2\cdot9+4\cdot7\cdot5[/tex]Taken mod 7, the first and last terms vanish and we're left with[tex]x\equiv72\equiv2\pmod7[/tex]which is what we want, so no adjustments needed here.[tex]x=7\cdot9\cdot3+4\cdot2\cdot9+4\cdot7\cdot5[/tex]Taken mod 9, the first two terms vanish and we're left with[tex]x\equiv140\equiv5\pmod9[/tex]so we don't need to make any adjustments here, and we end up with [tex]x=401[/tex].By the Chinese remainder theorem, we find that any [tex]x[/tex] such that[tex]x\equiv401\pmod{4\cdot7\cdot9}\implies x\equiv149\pmod{252}[/tex]is a solution to this system, i.e. [tex]x=149+252n[/tex] for any integer [tex]n[/tex], the smallest and positive of which is 149.