Vtgyjfy

Prove that prime $p$ different from $3$ is of the form $3k+1$ if and only if $p$ divides number of from $c^2+c+1$

i am trying but i did't get answer any hint please

Notice that if $pequiv 1$ mod 3, then $3$ divides $p-1=phi(p)$ where $phi$ is the euler function. This implies that there exists $c$ not congruent to 1 mod $p$ such that $c^3equiv 1$ mod p, (this is a fact from group theory). From this you can conclude that
$p$ divides $c^3-1=(c-1)(c^2+c+1)$. Since $p$ doesn't divide $c-1$ you have that $c^2+c+1$.

The other direction shouldn't be that hard.

(I just noticed that this is the solution Jyrki said in the comments).

Solution with Legendre symbol.

Say $p=6k+r$ where $rin {1,5}$ ($r$ can't be $0,2,3$ and $4$).

begin{eqnarray*}
pmid c^2+c+1 &Longleftrightarrow & pmid (2c+1)^2+3\
&Longleftrightarrow & -3equiv_p (2c+1)^2\
&Longleftrightarrow & Big({-3over p}Big) =1 \
&Longleftrightarrow & Big({-1over p}Big)cdot Big({3over p}Big)=1\
&Longleftrightarrow & Big({-1over p}Big)cdot Big({3over p}Big)=1\
&Longleftrightarrow & (-1)^{p-1over 2}cdot (-1)^{big[{p+1over 6} big]}=1\
&Longleftrightarrow & {p-1over 2}+ Big[{p+1over 6} Big]equiv_2 0\
&Longleftrightarrow & 3k+{r-1over 2}+ kBig[{r+1over 6} Big]equiv_2 0\
&Longleftrightarrow & {r-1over 2}+ Big[{r+1over 6} Big]equiv_2 0\
&Longleftrightarrow & r=1
end{eqnarray*}

Second solution (only one way)

Perhaps it would be easyer to see that $$c^2+c+1 equiv _6 1,3$$
Each prime that divide $c^2+c+1$ is $3$ or $6k+r$ where $r=1$ or $r=5$.
It is easy to see that the sets $$A={6a+1;;ain mathbb{Z}}$$ and $$B= {6b+5;;bin mathbb{Z}}$$
are closed for multiplication. And if we multiply $xin A$ and $yin B$ we get $xyin B$.

So if there is at least one $p equiv_6 5$, then product of all primes would be $equiv_6 5$ but this can be.

Solution using Einsenstein integers

The Eisenstein ring $E:=mathbf Z [omega]$ is the ring of integers of the quadratic field $mathbf Q(omega)$, where $omega$ is a primitive cubic root of unity. $E$ is a PID (even a Euclidian domain) in which the decomposition of the rational primes $p$ is classically known : (i) $p=3$ is totally ramified, more precisely $3$ is associate to $(1-omega)^2$ ; (ii) $pequiv-1pmod 3$ is inert, i.e. $p$ remains prime in $E$ ; (iii) $pequiv 1pmod 3$ is totally split, i.e. $p=pi.bar{pi}$, the product of two conjugates primes of $E$. The splitting case is equivalent to $p=N(pi)$ , where the norm $N$ is such that $N(a+bomega)=a^2 + b^2 - ab$ (see the hint of @Oscar Lanzi). Since $E$ is a PID, for any prime $pi$, the quotient $E/pi E$ is a finite field of order $N(pi)$, and case (iii) is equivalent to saying that $mathbf Z/pmathbf Z cong E/pi E$, or that $ (E/pi E)^*$ is a cyclic group of order $N(pi)-1=p-1$.

Now, sticking to case (iii), fix a generator $g$ of $(E/pi E)^*$, so that $x=g^{frac {p-1}{3}}$ is a cubic root of unity in $(E/pi E)^*$. But $x^3 - 1= (x-1)(x-omega)(x-omega^2)$ in $ (E/pi E)^*$, where the three cubic roots of unity are easily seen to be distinct. It follows that case (iii) is equivalent to saying that $g^{frac {p-1}{3}}$ is a root of $(x-omega)(x-omega^2)=x^2 +x + 1$. Using the isomorphism $mathbf Z/pmathbf Zcong E/pi E$, this is in turn equivalent to $c^2+c+1=0$ in $(mathbf Z/pmathbf Z)^*$, where $c$ corresponds to $g^{frac {p-1}{3}}$ .

Of course, the above argument appears unduly complicated compared to those of @Jose Cruz or @John Watson. But it presents the advantage to surrepticiously introduce Legendre's symbol of cubic residues, which can be defined as follows. In both cases (ii) and (iii), if $pi$ is a prime of $E$ not dividing $alpha in E$, obviously $alpha^{N(pi)-1}equiv 1pmod pi$. Note that $N(pi)=p^2$ in case (ii), so that, as previously, $alpha^{frac{N(pi)-1}{3}}equiv 1, omega,omega^2 pmod pi$ in both cases (ii) and (iii). The Legendre symbol $(alpha /pi)_3$ is then defined to be the unique cubic root of unity s.t. $alpha^{frac{N(pi)-1}{3}}equiv (alpha /pi)_3pmod pi$. The cyclicity of $(E/pi E)^*$ implies that $(alpha /pi)_3=1$ iff $x^3equiv alpha pmod pi$ has a solution in $E$ .