Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple ( ? ) congruence

  1. Mar 27, 2005 #1
    I have to show that this congruence has solutions:

    x^2 == -23 ( mod 4*59)

    i dont think i can use the legendre symbol for that bc 4* 59 is even.

    can i use the jacobi symbol ? ( -23 /4*59) or does it have to be odd too ?
  2. jcsd
  3. Mar 27, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Firstly I'd check what properties any solution would have, namely

    x^2= -23 = 1 mod 4
    x^2=-23 = 36 mod 59.

    so x =+/-9 mod 59 and x=1,3 mod 4

    and i'd find what these translate to mod 236 (chinese remainder theorem)
  4. Mar 28, 2005 #3
    Errata: so x =+/-9 mod 59 and x=1,3 mod 4, that's x=+/-6.
    This then gives us four solutions.
  5. Mar 28, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    sorry, indeed i mean x=+/-6 mod (59)

    (note your errata has an erratum in it, it fails to mention which one i buggered up.)
  6. Mar 28, 2005 #5
    Gee whiz! i was trying not to call attention to you personally! Sorry.
  7. Mar 30, 2005 #6
    but by doing what u guys said..that would give me the solutions to the congruence. I dont really need to find them. Is there maybe another way to do it, just to show that it has solutions, without actually finding them?
  8. Mar 31, 2005 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    There is no way I know of to do it, but that means little. Looking at the known methods for these things they need odd numbers. Do you think it was just coincidence that 23 happened to be an obvious square both modulo 4 and modulo 59?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Simple ( ? ) congruence
  1. Notion of Congruence (Replies: 23)

  2. Congruence Proof (Replies: 0)

  3. Congruence Solving (Replies: 6)

  4. Congruence relation (Replies: 0)