Results 1 to 4 of 4

Math Help - Prime divisors of n^2 + n + 1

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Prime divisors of n^2 + n + 1

    Prove that for ANY integer n, n^2+n+1 has no prime divisors of the form 6m-1.
    ==========================================

    Attempt:
    Let p be a prime divisor of n^2+n+1.
    Then n^2+n+1 0 (mod p)
    => n^3 -1 = (n-1)(n^2+n+1) 0 (mod p)
    => n^3 ≡ 1 (mod p)
    Let e_p(n) = order of n mod p
    => e_p(n)|3
    => e_p(n)= 1 or 3

    Now I'm stuck here. How to finish the proof from here?

    Any help is greatly appreciated!


    [also under discussion in math links forum]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by kingwinner View Post
    Prove that for ANY integer n, n^2+n+1 has no prime divisors of the form 6m-1.
    ==========================================

    Attempt:
    Let p be a prime divisor of n^2+n+1.
    Then n^2+n+1 0 (mod p)
    => n^3 -1 = (n-1)(n^2+n+1) 0 (mod p)
    => n^3 ≡ 1 (mod p)
    Let e_p(n) = order of n mod p
    => e_p(n)|3
    => e_p(n)= 1 or 3

    Now I'm stuck here. How to finish the proof from here?

    Any help is greatly appreciated!


    [also under discussion in math links forum]
    see here for two solutions.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    From your solution...

    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+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by kingwinner View Post
    From your solution...



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

    Thanks!
    we assumed that p \mid n^2+n+1, which means n^2+n+1=kp, for some integer k. then 4n^2+4n+4=4kp and so (2n+1)^2+3=4kp. thus (2n+1)^2 \equiv -3 \mod p, which means -3

    is a quadratic residue modulo p and so \left (\frac{-3}{p} \right)=1.
    Last edited by NonCommAlg; March 9th 2010 at 08:54 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relitivly prime, unique divisors of divisors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 24th 2010, 08:40 AM
  2. Divisors from Prime Factors
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 3rd 2009, 06:42 AM
  3. Odd prime divisors
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 1st 2008, 11:39 AM
  4. Number Theory - Prime divisors
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 10th 2007, 06:05 AM
  5. Prime Numbers and common divisors
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 1st 2006, 06:54 PM

Search Tags


/mathhelpforum @mathhelpforum