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

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

Printable View

- Dec 6th 2009, 11:36 PMroninproInteger-valued polynomial
I came across this problem when I was going through Yahoo answers.

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

$\displaystyle \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. $ - Dec 7th 2009, 04:34 AMPaulRS
Note that $\displaystyle 1+n+n^2 = \tfrac{n^3-1}{n-1}$. So if $\displaystyle p|(1+n+n^2)$ then $\displaystyle p|(n^3-1)$

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

Hence we must have $\displaystyle \text{ord}_p(n)=3$, but then $\displaystyle 3|(p-1)$ - by Fermat's Little Theorem- which is again a contradiction! - Mar 9th 2010, 07:51 PMkingwinner
- Mar 10th 2010, 07:19 PMroninpro
The idea in NonCommAlg's post was to look at the equation $\displaystyle 1+n+n^2\equiv 0\pmod{p}$, where $\displaystyle p=6k+5$ for some integer $\displaystyle k$. Multiplying both sides by 4 gives $\displaystyle 4+4n+4n^2\equiv 0\pmod{p}$. Subtracting 3 from both sides gives $\displaystyle 1+4n+4n^2\equiv -3\pmod{p}$. We factor the left hand side: $\displaystyle (2n+1)^2\equiv -3\pmod{p}$.

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