Find all positive integer $n$ that satisfy$ \ n^{2019} \equiv 7 \pmod{2019}$ where $1<n<2019$
Honestly, I have no idea how to manage this problem. I just knew about Fermat's little theorem , but seems like it doesn't help me at all to solve this problem.
Maybe we try to solve $ \ n^{2019} \equiv 1 \pmod{2019}$ and $n$ is a number multiple of $7$ ?
Thank you and I appreciate any help.
Best Answer
From CRT we have the system
$x^{2019}\equiv 7\bmod 3$
$x^{2019}\equiv 7\bmod 673$
The first equation reduces to $x=1\bmod 3$ via $x^{n+2}\equiv x^n\bmod 3$ for all $n\ge 1$ (Fermat). So we have one residue $\bmod 3$.
Now for the fun part. What becomes of the second equation?
Fermat's result gives $x^{2019}\equiv x^{1347}\equiv x^{675}\equiv x^3\bmod 673$. So everything turns on whether $7$ is a cubic residue $\bmod 673$. With $673$ being one greater than a multiple of $3$ there are either three roots or none.
If $7$ is a cubic residue $\bmod 673$ then $7^{224}\equiv 1$. Test this with the squaring and multiplication method of exponentiation:
$7^2\equiv 49$
$7^3\equiv 343$
$7^6\equiv 547$
$7^7\equiv 464$
$7^{14}\equiv 609$
$7^{28}\equiv 58$
$7^{56}\equiv 672$
$7^{112}\equiv 1$
$\color{blue}{7^{224}\equiv 1}$
The test passes. We then have $x\equiv 7^{1/3}\equiv (7^{225})^{1/3}\equiv 7^{75}\bmod 673$. Using the squaring and multiplication method again gives $194$.
We have two more cube roots which must have the form
$-97(1\pm\sqrt{-3})\bmod 673$
in order for all three roots to sum to zero and give a product of $194^3\equiv 7$. Let us render
$\sqrt {-3}\equiv\sqrt{-676}\equiv26\sqrt{-1}\equiv26\sqrt{5×673-1}\equiv26\sqrt{3364}\equiv26×58\equiv162$
(We could have also rendered $\sqrt{-1}\equiv 58$ from the cubic residue test above, as $58$ precedes $672$ in the squaring process.)
Then the remaining cube roots are
$-97(1\pm162)\equiv \{138,341\}\bmod 673$
And so we have our modulo $3$ and modulo $673$ components
$x\equiv 1\bmod 3$
$x\in\{138,194,341\}\bmod 673$
Finally: take each residue from the $\bmod 673$ equation and add $673$ successively until we get a result satisfying the $\bmod 3$ equation. Thereby
$\color{blue}{x\in\{811,1540,1687\}\bmod 2019}$