1
$\begingroup$

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.

Thanks in advance!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – hardmath Aug 18 at 17:31
  • $\begingroup$ Thought $3x \equiv 0 mod 9$ iff $3x = 9q$ with q an integer so $x = 3q$. $\endgroup$ – Kabouter9 Aug 18 at 17:33
  • 1
    $\begingroup$ 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$. $\endgroup$ – AgentS Aug 18 at 17:43
  • 1
    $\begingroup$ @ganeshie8 Isn't "unique solutions" an oxymoron? $\endgroup$ – fleablood Aug 18 at 21:30
  • 2
    $\begingroup$ I didn't say the OP didn't do it correctly. I asked the OP to tell us what he was doing and why. $\endgroup$ – fleablood Aug 18 at 21:34
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$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)}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.