Results 1 to 4 of 4

Math Help - [SOLVED] quadratic residues congruence problem

  1. #1
    Senior Member
    Joined
    Feb 2008
    Posts
    410

    [SOLVED] quadratic residues congruence problem

    list all solutions of...the ten congruences x^2\equiv a\mod 11^2 where a=1,3,4,5,9.
    We know that each congruence has two solutions, and that if we can find one solution x\equiv s then the second solution is x\equiv-s. But I don't know any algorithms I can use to solve each of the first solutions, except trial and error, which of course is far too inefficient.

    This is an exercise in the chapter for quadratic residues, so presumably that has something to do with it.

    Any ideas would be appreciated.
    Last edited by hatsoff; November 19th 2009 at 06:57 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Well first off solving  x^2 \equiv 1 \mod{p} is easy:  x = \{-1,1\} .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quite so.

    And of course if \sqrt{a}\in\mathbb{Z} then x\equiv\pm\sqrt{a} are solutions to x^2\equiv a\mod 11^2. So cases a=1,4,9 are easy to solve in that manner.

    However, for cases a=3,5, I am at a loss for an efficient method.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by hatsoff View Post
    We know that each congruence has two solutions, and that if we can find one solution x\equiv s then the second solution is x\equiv-s. But I don't know any algorithms I can use to solve each of the first solutions, except trial and error, which of course is far too inefficient.

    This is an exercise in the chapter for quadratic residues, so presumably that has something to do with it.

    Any ideas would be appreciated.

    Since 5^2=6^2=3\!\!\!\!\pmod{11} , the solutions for the same congruence modulo 11^2 have to be 5\,,\,6\!\!\!\!\pmod{11} , so you have to check "only" these cases:

    5,16,27,38,49,60,71,82,93,104,115...and indeed 27^3=(-27)^2=94^2=3\!\!\!\!\pmod{121}.

    Do something simmilar with the rest.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. one more quadratic residue congruence problem please
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 20th 2009, 10:27 AM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 12th 2009, 10:42 AM
  3. Solving for x in a quadratic congruence modulo problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 12th 2009, 09:32 PM
  4. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 07:45 PM
  5. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2007, 12:14 PM

Search Tags


/mathhelpforum @mathhelpforum