Prove that a prime factor of a quantity satisfies a congruence

Question

Let $K = (3n)^2 + 3n + 1$. I've shown that if a prime $p$ divides $K$ then $3n$ has order 3 in the group $\mathbb F_p^\times$. Using this, I'm trying to show that $p \equiv 1 \pmod 3$, but I'm stuck. I think I might need to use quadratic reciprocity somehow.

Answer 1

There are two ways you can go about this, using order and using discriminant.

Using group theory

We can see that $p \mid (3n)^2+3n+1 \implies p \mid (3n)^3-1$. This shows that $(3n)^3 \equiv 1 \pmod{p}$ or that $3n$ has order $3$ in $\mathbb{F}_p$. This gives us $3 \mid (p-1)$ or $p \equiv 1 \pmod{3}$ since $p-1$ is the order of the group. An equivalent way of solving this is saying that $3$ is the order of $3n$ modulo $p$, and thus $3 \mid \phi(p)$. Since $\phi(p)=p-1$, we have $3 \mid (p-1)$ or $p \equiv 1 \pmod{3}$.

Using discriminant

If prime $p$ has to divide a quadratic $ax^2+bx+c$, we can see that the discriminant of this equation has to be a quadratic residue modulo $p$. The discriminant of $(3n)^2+3n+1$ is $b^2-4ac=(1)^2-4(1)(1)=-3$. This gives: $$\bigg(\frac{-3}{p}\bigg)=1 \implies p \equiv 1 \pmod{3}$$