1. ## Integer-valued polynomial

I came across this problem when I was going through Yahoo answers.

Show that the values of the polynomial $f(n)=1+n+n^2$ have no prime factors of the form $5 \pmod{6}$ for any $n\in \mathbb{Z}$.

2. Originally Posted by roninpro
I came across this problem when I was going through Yahoo answers.

Show that the values of the polynomial $f(n)=1+n+n^2$ have no prime factors of the form $5 \pmod{6}$ for any $n\in \mathbb{Z}$.
straightforward: suppose there exists a prime $p \equiv 5 \mod 6$ such that $p \mid n^2+n+1,$ for some $n \in \mathbb{N}.$ then $(2n+1)^2 \equiv -3 \mod p.$ therefore $\left (\frac{-3}{p} \right) = 1,$ which is a contradiction because:

$\left (\frac{-3}{p} \right)= (-1)^{\frac{p-1}{2}} \left (\frac{3}{p} \right )= (-1)^{\frac{p-1}{2}} \cdot (-1)^{\frac{p-1}{2}} \left (\frac{p}{3} \right )=\left (\frac{2}{3} \right )=-1.$

3. Note that $1+n+n^2 = \tfrac{n^3-1}{n-1}$. So if $p|(1+n+n^2)$ then $p|(n^3-1)$

Evidently $p$ can't divide $(n-1)$ since then we'd have $1+n+n^2\equiv 3 (\bmod.p)$ which would mean that $p=3$ -since p|(1+n+nē) -

Hence we must have $\text{ord}_p(n)=3$, but then $3|(p-1)$ - by Fermat's Little Theorem- which is again a contradiction!

4. Originally Posted by NonCommAlg
then $(2n+1)^2 \equiv -3 \mod p.$ therefore $\left (\frac{-3}{p} \right) = 1$
Can you explain why this part is true? Where did you get 2n+1? and why is it conrugent to -3 (mod p)?

Thanks!

5. Originally Posted by kingwinner
Can you explain why this part is true? Where did you get 2n+1? and why is it conrugent to -3 (mod p)?

Thanks!
The idea in NonCommAlg's post was to look at the equation $1+n+n^2\equiv 0\pmod{p}$, where $p=6k+5$ for some integer $k$. Multiplying both sides by 4 gives $4+4n+4n^2\equiv 0\pmod{p}$. Subtracting 3 from both sides gives $1+4n+4n^2\equiv -3\pmod{p}$. We factor the left hand side: $(2n+1)^2\equiv -3\pmod{p}$.

My original idea was somewhat similar. I first looked at the quadratic equation: $x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$. This can be interpreted as a formula modulo $p$ by making a few modifications. We should take $\frac{1}{2a}$ to mean $(2a)^{-1}$ and $\sqrt{\ \ }$ to mean the square root modulo $p$. (If you are not comfortable with this, try actually completing the square and solving for $x$, all modulo $p$.) Then, it follows that a quadratic polynomial modulo $p$ has roots if and only if the discriminant $b^2-4ac$ is a quadratic residue. In the case of the problem, $b^2-4ac=-3$ (it is not a coincidence that this is the same as in the above), and we can apply the reciprocity argument as NonCommAlg outlined already.