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.

I know about the Legendre symbol and quadratic reciprocity

  • $\begingroup$ What have you learned about quadratic residues? Please edit this into your question rather than add a comment. $\endgroup$ – Erick Wong Mar 10 '18 at 23:48
  • 1
    $\begingroup$ Do not delete questions that received an answer. $\endgroup$ – 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, $$

which leads to a contradiction.

  • $\begingroup$ I think i just need to look at this over but where does the $-3$ come from? $\endgroup$ – Jorved Mar 11 '18 at 1:37
  • $\begingroup$ Because $12n^2 \equiv -1 \pmod p$ means $(6n)^2 \equiv -3 \pmod p$. $\endgroup$ – Hw Chu Mar 11 '18 at 1:38
  • $\begingroup$ How did you come to $(-3|p)=1$, what if you let $p≡1(mod)6$, how does $(-3|p)$ change? $\endgroup$ – Jorved Mar 11 '18 at 3:02
  • $\begingroup$ 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$. $\endgroup$ – Hw Chu Mar 11 '18 at 3:07
  • $\begingroup$ 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. $\endgroup$ – Hw Chu Mar 11 '18 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.