# Solving system Chinese Remainder Theorem

I have to calculate $$2019x \equiv18^{2019} \, mod \, 45$$

This is equivalent to: $$\begin{cases} 2019x \equiv 18^{2019} \, \text{mod} \, 5 \\ 2019x \equiv 18^{2019} \, \text{mod} \, 9 \end{cases}$$ We know that $$2019x \, mod \, 5 = 4x$$ and $$2019x \, mod \, 9 = 3x$$. So we get: $$\begin{cases} 4x \equiv 1 \, \text{mod} \, 5 \\ 3x \equiv 0 \, \text{mod} \, 9 \end{cases}$$. We can now multiply by the inverses. So we get: $$\begin{cases} x \equiv 4 \, \text{mod} \, 5 \\ x \equiv 0 \, \text{mod} \, 3 \end{cases}$$. The last step will be here to use the Chinese Remainder theorem. I'm asking if my method is correct because it is the first time I'm practicing this kind of questions and I want to be sure.

• I think the congruence mod $5$ starts with a wrong right hand side, and the congruence mod $9$ is a little tricky because $9$ is not a prime (but it is a power of a prime). Check over your work. – hardmath Aug 18 at 17:31
• Thought $3x \equiv 0 mod 9$ iff $3x = 9q$ with q an integer so $x = 3q$. – Kabouter9 Aug 18 at 17:33
• Looks good to me... using CRT you will get one unique solution in mod $15$. Then you can add multiples of $15$ to that to get unique solutions in mod $45$. – AgentS Aug 18 at 17:43
• @ganeshie8 Isn't "unique solutions" an oxymoron? – fleablood Aug 18 at 21:30
• I didn't say the OP didn't do it correctly. I asked the OP to tell us what he was doing and why. – fleablood Aug 18 at 21:34

The method is correct but it should be $$\!\bmod 5\!:\ {-}x\equiv 4x\equiv \color{#c00}2,\,$$ so $$\,x\equiv -2\equiv 3,\,$$ and also $$\,x\equiv 0\equiv 3\pmod{\!3} \iff x\equiv 3\pmod{\!15}\,$$ by LCM or CCRT = Constant case CRT.
$$18^{2019} \equiv (-2)(-2)^{2018} \equiv (-2)(-1)^{1009} \equiv 2 \text{ (mod 5)}$$
$$2019 x \equiv -x \equiv 2 \Rightarrow x \equiv 3 \text{ (mod 5)}$$
Luckily, the second congruence is $$x \equiv 0 \text{ (mod 3)}$$. No need for CRT, since 3|3
Combine both congruences: $$x \equiv 3 \text{ (mod 15)}$$