# Prove that every prime factor of $12x^2+1$ has the form $6n+1$

Let $n$ be an integer, prove that every prime factor of $12x^2+1$ has the form $6m+1$, where $m$ is an integer.

I've gone as far as knowing that all primes $p>3$ are either $6m+1$ or $6m-1$, how do I use this, not sure whether to even use that.

• Do not delete questions that received an answer. – quid Mar 11 '18 at 1:06

2 and 3 can be easily excluded, so let $p$ be a prime which is at least 5.

Then $p$ is either congruent to 1 or 5 modulo 6. Suppose $p \ | \ 12n^2 + 1$ and $p \equiv 5 \pmod 6$. Then we have $12n^2 \equiv -1 \pmod p$ and hence

$$\Big(\frac{-3}{p}\Big) = 1,$$

where $()$ is the Legendre symbol. By the rules of Legendre symbol and the quadratic reciprocity, we have

$$\Big(\frac{-3}{p}\Big) = \Big(\frac{-1}{p}\Big)\Big(\frac{3}{p}\Big) = (-1)^{\frac{p-1}{2}} (-1)^{\frac{2\times(p-1)}{4}} \Big(\frac{p}{3}\Big) = \Big(\frac{p}{3}\Big) = -1,$$

• I think i just need to look at this over but where does the $-3$ come from? – Jorved Mar 11 '18 at 1:37
• Because $12n^2 \equiv -1 \pmod p$ means $(6n)^2 \equiv -3 \pmod p$. – Hw Chu Mar 11 '18 at 1:38
• How did you come to $(-3｜p)=1$, what if you let $p≡1(mod)6$, how does $(-3｜p)$ change? – Jorved Mar 11 '18 at 3:02
• Please see the computations above. That is a result by multiplicative law of (), formula for $(\frac{-1}p)$, and the reciprocity law. If $p \equiv 1 \pmod 6$ then $(\frac{-3}p) = (\frac p3) = 1$. – Hw Chu Mar 11 '18 at 3:07
• From the first line of my comment, $(6n)^2 \equiv -3 \pmod p$, so $-3$ is a quadratic residue and hence $(\frac{-3}{p})$ has to be 1 by the definition of Legendre symbol. – Hw Chu Mar 11 '18 at 3:11