If $p\equiv 1 \;\text{mod}\; 3$, then show that one can find an integer $k$ satisfying $k^2-k+1=p\cdot M\;$ with $M<p$

Question

If $p\equiv 1 \;\text{mod}\; 3$, then show that one can find an integer $k$ satisfying $k^2-k+1=p\cdot M\;$ with $M<p$ ($p$ is a prime)

I don't have any clue on how to work this problem. Also, if i can find such $k$ how do i prove that $M<p$ and we can always find such a $M$. Can someone please help me in solving this question.

Edit: Take $p=7$ then $p\equiv 1 \;\text{mod}\; 3$ but there is no integer $r$ satisfying $k^2-k+1=p\cdot M$ for $M=2,4,5,6$

Now I am more confused.

Answer 1

Note that $(r^2 - r + 1)(r+1) = r^3 + 1$

If $p \equiv 1 \pmod 3$ then $p = 3k+1$ and $x^{3k+1} \equiv x \pmod p$ by Fermat's little theorem.

• $x^{3k+1} \equiv x \pmod p$
• $x^{3k} \equiv 1 \pmod p$
• $(x^{k})^3 \equiv 1 \pmod p$
• $(-x^{k})^3 \equiv -1 \pmod p$
• $(-x^{k})^3 + 1 \equiv 0 \pmod p$

Let's do an example, $p=7$ pick a random $x$, $x=2$ then $-x^{(7-1)/3} = 3$ and indeed $3^2 - 3 + 1 \equiv 0 \pmod 7$.

Answer 2

The discriminant of $r^2-r+1$ is $-3$ and by quadratic reciprocity law we have: $(-3|p)=(-1|p)(3|p)=(p|3)=1$ Hence, there exists $r$ such that $0<r<p$ and $r^2-r+1\equiv 0\pmod p$. Since $0<r^2-r+1<p^2$, the assertion follows.