Results 1 to 6 of 6

Math Help - Finding square roots mod n

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Finding square roots mod n

    Hi, how can I find all four solutions to x^2 133 (mod 143)?
    Last edited by posix_memalign; October 4th 2009 at 07:39 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello posix_memalign
    Quote Originally Posted by posix_memalign View Post
    Hi, how can I find all four solutions to x2 133 (mod 143)?
    I cheated, I suppose, and used a spreadsheet to do the arithmetic, by looking at the values of 143n+133, to see where the perfect squares came. This gave answers of x = 43, 56, 87, 100. But, perhaps you want a more mathematical method ...

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by Grandad View Post
    Hello posix_memalignI cheated, I suppose, and used a spreadsheet to do the arithmetic, by looking at the values of 143n+133, to see where the perfect squares came. This gave answers of x = 43, 56, 87, 100. But, perhaps you want a more mathematical method ...

    Grandad
    Thanks.
    I wrote a program prior to asking which determined the correct answers as well -- they are the same as yours -- although yes, I was looking for the 'right' way of doing this, i.e. mathematical approach.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by posix_memalign View Post
    Hi, how can I find all four solutions to x^2 133 (mod 143)?
    I was looking for the 'right' way of doing this, i.e. mathematical approach.
    There is no 'right' way, but there are several approaches that ease the pain.
    Notice that 143 is composite and its factors are 11 & 13.

    133 mod 11 is 1
    133 mod 13 is 3

    You are looking for a number that is both
     x^2 \equiv 1 mod 11
    &
     x^2 \equiv 3 mod 13

    The chinese remainder theorem will assist in finding the answers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Chinese Remainder Theorem

    Hello everyone

    Thanks to aidan for this helpful posting:
    Quote Originally Posted by aidan View Post
    There is no 'right' way, but there are several approaches that ease the pain.
    Notice that 143 is composite and its factors are 11 & 13.

    133 mod 11 is 1
    133 mod 13 is 3

    You are looking for a number that is both
     x^2 \equiv 1 mod 11
    &
     x^2 \equiv 3 mod 13

    The chinese remainder theorem will assist in finding the answers.
    This does indeed give the solutions without any particular pain!

    x^2\equiv 1 \mod 11

    \Rightarrow x \equiv1, 10 \mod 11

    and

    x^2\equiv 3 \mod 13

    \Rightarrow x \equiv 4,9\mod 13

    Using the Euclidean Algorithm, we find that 6\times11+(-5)\times13 = 1

    and using the Chinese Remainder Theorem for the 4 pairs of values of x that we've found above we get:

    x\equiv1\mod11 and
    x\equiv4\mod13

    \Rightarrow x=66\times4+(-65)\times1

    =199

    \equiv56\mod143


    x\equiv1\mod11 and x\equiv9\mod13

    \Rightarrow x=66\times9+(-65)\times1

    =529

    \equiv100\mod143

    ... and so on.


    Grandad
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Grandad, thanks for finishing the post.
    Good explanation.
    Yesterday, the forum was extremely slow, and twice it would not respond.
    I did not attempt a third time.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. factorization by finding modular square roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 25th 2011, 10:45 AM
  2. Square roots.
    Posted in the Algebra Forum
    Replies: 18
    Last Post: September 6th 2010, 10:32 AM
  3. square roots
    Posted in the Algebra Forum
    Replies: 4
    Last Post: February 9th 2009, 05:30 AM
  4. Square Roots
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: February 28th 2006, 06:35 AM

Search Tags


/mathhelpforum @mathhelpforum