Sum of the first four positive integer $ \ a \ $ such that $ \ a^{2019} \pmod{2019 }= 1$

Question

I've tried many times via Euler's Theorem.

$ \varphi( 2019) = 2\times 672 = 1344 $

$a^{\varphi(2019)} \equiv a^{1344}\equiv 1 \mod 2019$

then , $a^{2019} \equiv a^{675} \mod 2019$ , obviously $1$ is 1 of 4 for answers and then how we can find another integer.

p.s. according to wolframalpha they've shown $3$ equation for integer solutions

I really appreciate for your help .

Answer 1

As $2019=3\cdot673$

From the given condition

$a^{2019}\equiv1\pmod{673}$

But $2019\equiv3\pmod{\phi(673)}$

So, $a^3\equiv1\pmod{673}$

which has exactly three solutions

Trivially, $a\equiv1$

Else $a^2+a+1\equiv0\pmod{673}$

$\iff(2a+1)^2\equiv-3$ which is solvable as Prove that $-3$ is a quadratic residue mod an odd prime $>3$ if and only if $p$ is of the form of $6n+1$

Similarly $$1\equiv a^{2019}\equiv a^1\pmod3$$ as $\phi(3)=2$

So using http://mathworld.wolfram.com/ChineseRemainderTheorem.html, we should have exactly three solutions $\pmod{3\cdot673}$

Answer 2

Hint $ $ Since $\ a^n\equiv 1\equiv a^k\,\Rightarrow a^{\gcd(n,k)}\equiv 1,\,$ we deduce $\,a^3\equiv 1$ so the sum of the first three roots is $\equiv 1+a+a^2\equiv 0,\,$ so the sum of the first four roots = fourth root = least root $(=1) + 2019$

Update $ $ Primitive roots are not known so we give a direct proof that if $p$ is prime and $3\mid p-1\,$ then $\,x^3-1\,$ has $\,3\,$ roots in the field $\,\Bbb Z_p = $ integers $\!\bmod p.\,$ Note $\,3\mid p-1\,\Rightarrow\, x^3-1\mid x^{p-1}-1\,$ so $\,x^{p-1}-1 = (x^3-1)f(x)\,$ for a polynomial $\,f(x)\,$ with integer coef's. Since a polynomial over a field has no more roots than its degree, if $\,x^3-1\,$ had less than $\,3\,$ roots then $\,(x^3-1)f(x)\,$ would have less than $\,p-1\,$ roots, contra it equals $\,x^{p-1}-1\,$ with $\,p-1\,$ roots, all $\,x\not\equiv 0,\,$ by little Fermat.