Results 1 to 4 of 4

Math Help - Mod 2011

  1. #1
    Newbie Sorombo's Avatar
    Joined
    Feb 2011
    Posts
    13

    Mod 2011

    Hi guys, I'm new at number theory. So, Could you help with the following congruence equation.


    $x^2+x+1676 \equiv 0 \mod 2011$


    Regards!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: Mod 2011

    Quote Originally Posted by Sorombo View Post
    Hi guys, I'm new at number theory. So, Could you help with the following congruence equation.


    x^2+x+1676 \equiv 0 \mod 2011
    I think that this equation has no solutions. I started by writing it as x^2 + x - 335\equiv0\pmod{2011} (since 1676\equiv-335\pmod{2011}). The usual formula for a quadratic equation gives the solutions as x = \tfrac12(-1\pm\sqrt{1341}), which you have to write as x\equiv1006(-1\pm\sqrt{1341})\pmod{2011} because 1006 is the inverse of 2 (mod 2011).

    So we need to know whether 1341 has a square root (mod 2011). In the technical jargon, is 1341 a quadratic residue (mod 2011)? The easiest way to investigate that is to notice that 1341 is the inverse of 3 (mod 2011). So 1341 will be a quadratic residue if and only if 3 is. By Euler's criterion (which we can apply because 3 and 2011 are both prime), that will be the case if and only if 3^{1005}\equiv1\pmod{2011}. But you can evaluate 3^{1005}\pmod{2011} by writing 1005 = 512+256+128+64+32+8+4+1 and calculating those powers of 3 (mod 2011) by successive squaring and reducing mod 2011. The answer comes out as 1, not 1.

    Thus 3 is not a quadratic residue (mod 2011) and therefore that congruence has no solutions.

    Edit. If you know about quadratic reciprocity, then you can avoid the calculation of 3^{1005}\pmod{2011} and get the result much more painlessly.
    Last edited by Opalg; November 16th 2011 at 12:36 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie Sorombo's Avatar
    Joined
    Feb 2011
    Posts
    13

    Re: Mod 2011

    I have a point I'd like to check, how could I prove that x is a quadratic residue modulo p if and only if its inverse is?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: Mod 2011

    Quote Originally Posted by Sorombo View Post
    I have a point I'd like to check, how could I prove that x is a quadratic residue modulo p if and only if its inverse is?
    If x=y^2 then x^{-1} = (y^{-1})^2, and conversely.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. IMO 2011 (Problem 6)
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: July 19th 2011, 09:14 AM
  2. IMO 2011 (Problem 5)
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: July 19th 2011, 09:06 AM
  3. IMO 2011 (Problem 1)
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 19th 2011, 02:40 AM

Search Tags


/mathhelpforum @mathhelpforum