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

Square root of 1 with mod how to prove it?

  1. Oct 6, 2009 #1
    I know that if n is odd and has k distinct prime factors, then the number of roots, x^2 = 1 (mod n), is equal to 2^k.
    However, I don't know how to give a formal proof to it.
    I simply want to bypass the generalized form x^2 = a (mod n).
    How can I prove it directly?
    Thank you.
     
  2. jcsd
  3. Oct 6, 2009 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Hmm... assuming it holds mod p^k, you could just CRT the results together.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook