Results 1 to 5 of 5

Math Help - Determine which primes > 3 divide...

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    34

    Determine which primes > 3 divide...

    Determine which primes > 3 divide some number of the form 3n^2 - 5n + 1 and which do not.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Since  p>3, \; (3,p)=1 \implies 3^{-1} exists. Let  a_p\equiv3^{-1} \bmod{p} .

    Set  3n^2+5n-1\equiv0\bmod{p}\implies n^2+5a_pn-a_p\equiv0\bmod{p}\implies n^2+5a_pn\equiv a_p\bmod{p} .


    Complete the square:

     (n+5\cdot2^{-1}\cdot a_p)^2\equiv 3^{-1}+25\cdot 4^{-1}\cdot a_p^2 \bmod{p}

    (again  2^{-1} and  4^{-1} exist since  p>2 ).


    So a solution exists (i.e.  p divides this polynomial for some  n )  \iff \left(\frac{3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}}{p}\right)  = 1, where  \left(\frac xp\right) is the Legendre symbol.

    Pretty messy huh?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by chiph588@ View Post
    Since  p>3, \; (3,p)=1 \implies 3^{-1} exists. Let  a_p\equiv3^{-1} \bmod{p} .

    Set  3n^2+5n-1\equiv0\bmod{p}\implies n^2+5a_pn-a_p\equiv0\bmod{p}\implies n^2+5a_pn\equiv a_p\bmod{p} .


    Typo: it must be 3n^2-5n+1=0\!\!\!\pmod p\Longrightarrow n^2-5a_pn+a_p=0\!\!\!\pmod p \Longrightarrow n^2-5a_pn=-a_p\!\!\!\pmod p


    Complete the square:

     (n+5\cdot2^{-1}\cdot a_p)^2\equiv 3^{-1}+25\cdot 4^{-1}\cdot a_p^2 \bmod{p}


    It must be: (n-5\cdot 2^{-1}a_p)^2=(-3^{-1}+25\cdot 4^{-1}\cdot 9^{-1})\!\!\!\pmod p



    (again  2^{-1} and  4^{-1} exist since  p>2 ).


    So a solution exists (i.e.  p divides this polynomial for some  n )  \iff \left(\frac{3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}}{p}\right) = 1,



    [color=red]"...if \left(\frac{-3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}}{p}\right) = 1"

    Pretty nice piece of work, indeed!

    Tonio

    where  \left(\frac xp\right) is the Legendre symbol.

    Pretty messy huh?
    .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by tonio View Post
    .

    Not only the above tells you what primes divide the quadratic in n but it also tells you how to find the n's!

    For example, take p=13\Longrightarrow it must be that -3^{-1}+25\cdot 4^{-1}\cdot 9^{-1} is a square modulo 13, but:

    -3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}=-9-1\cdot 10\cdot 3=-9-30=-39=0\!\!\!\pmod{13}\Longrightarrow we've a solution for each n s.t. (n-5\cdot 2^{-1}\cdot3^{-1})^2=(n-5\cdot 7\cdot 9)^2=(n-3)^2= 0\!\!\!\pmod{13}\iff n=3\!\!\!\pmod{13} , and choosing n=3 we indeed get 3\cdot 9-5\cdot 3+1=13=0\!\!\!\pmod{13}

    And with 16=3\!\!\!\pmod{13}\,,\,\,3\cdot 16^2-5\cdot 16+1=689=13\cdot 53=0\!\!\!\pmod {13} and etc.

    Very beautiful

    Tonio
    Last edited by tonio; April 13th 2010 at 06:11 PM. Reason: Correcting typo: p = 13 instead of original n = 13
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Whoops! Typo's!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] gcd(a,b) = 1 iff no primes divide a and b
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 12th 2011, 04:04 AM
  2. [SOLVED] How to divide GCF through...
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 1st 2011, 04:15 PM
  3. Divide
    Posted in the Algebra Forum
    Replies: 1
    Last Post: June 2nd 2010, 02:52 PM
  4. Replies: 1
    Last Post: April 22nd 2009, 03:05 AM
  5. Let P be the set of primes that divide 200!.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2006, 07:20 PM

Search Tags


/mathhelpforum @mathhelpforum