Chinese Remainder for x= 7 (mod 8), x= 2 (mod 9), x= -1 (mod 5)

Question

So I'm not very good at the chinese remainder theorem, but I think that x being 551 works. But I'm not sure how the negative 1 affects the equation. Also, if x=551 works, then would you multiply 8×9×5=360 and then subtract 360 from 551 to get x= 191 (mod 360)? Any help on this would be great! Thank you!

Answer 1

Negative numbers follow the same rules as positive in modular equations so we can say $$x\equiv-1\equiv -1 + 5 \equiv 4\pmod{5} $$ The reason we might use them is that we can see that the first equation can be rewritten as $x\equiv -1\pmod{8}$, and then we can realize that $8*5-1 =39$ satisfies both $$8*5-1 \equiv -1 \pmod{5}$$ and $$8*5-1 \equiv -1 \pmod{8}$$ Unfortunately, however, $39 \equiv 3\pmod{9}$, so we're not done yet. We have to add a multiple of $40 \equiv 4\pmod{9}$ in order to make this number also $2\pmod{9}$. To do this, we must solve the equation $$39 + 40n \equiv 3 + 4n \equiv 2 \pmod{9}$$ Then we can rearrange this as $$4n \equiv 3-2 \equiv 8\pmod{9}$$ And see that $n=2$ solves it. Thus an answer is $39 + 40*2 = 119$. And as $5,8,9$ are all relatively prime, the solutions will be precisely $119 + 5*8*9k$ for $k\in \mathbb{Z}$.