Results 1 to 5 of 5

Thread: Integer-valued polynomial

  1. #1
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485

    Integer-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}$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by roninpro View Post
    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}$.
    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. $
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    405
    Quote Originally Posted by NonCommAlg View Post
    then $\displaystyle (2n+1)^2 \equiv -3 \mod p.$ therefore $\displaystyle \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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Quote Originally Posted by kingwinner View Post
    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 $\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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Dec 6th 2011, 11:47 AM
  2. Integer Valued Matrix
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: Dec 15th 2010, 07:56 PM
  3. Polynomial with integer solutions.
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Mar 2nd 2010, 09:34 AM
  4. An integer-valued function
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: Jun 24th 2009, 01:24 AM
  5. integer-valued function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 6th 2009, 06:20 AM

Search Tags


/mathhelpforum @mathhelpforum