Results 1 to 5 of 5

Math Help - 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 f(n)=1+n+n^2 have no prime factors of the form 5 \pmod{6} for any 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 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.
    Follow Math Help Forum on Facebook and Google+

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

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by NonCommAlg View Post
    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!
    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 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 6th 2011, 11:47 AM
  2. Integer Valued Matrix
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: December 15th 2010, 07:56 PM
  3. Polynomial with integer solutions.
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: March 2nd 2010, 09:34 AM
  4. An integer-valued function
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: June 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