Results 1 to 4 of 4

Math Help - square root of 1 (mod n). How to give a proof??

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    5

    square root of 1 (mod n). How to give a proof??

    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.
    I wish to go without proving the generalized form x^2 = a (mod n).
    How can I prove it directly?
    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Hint : use the Chinese Remainder Theorem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    5

    Request more clues

    But how?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2009
    Posts
    9
    Quote Originally Posted by jacquelinek View Post
    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.
    I wish to go without proving the generalized form x^2 = a (mod n).
    How can I prove it directly?
    Thanks.
    Factorize n = p_1*p_2*p_3*...*p_n where the p_i's are distinct

    now for each p_i solve the congruence equation

    x^2 = 1 (mod p_i)

    => p|(x^2 -1) => p |(x-1)(x+1)

    and since p is prime, p|x-1 or p|x+1 => x = 1 or -1 (mod p_i)

    ... ... ...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof that square root of a negative does not exist.
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: September 7th 2011, 07:03 PM
  2. proof that if a square is even then the root is too.
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: February 3rd 2011, 12:55 PM
  3. Uniqueness of Square Root proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 16th 2010, 01:19 PM
  4. Square Root Proof Problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 24th 2008, 07:10 AM
  5. Proof of square root being irrational
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 14th 2007, 02:07 PM

Search Tags


/mathhelpforum @mathhelpforum