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

• Oct 5th 2009, 11:35 PM
jacquelinek
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.
• Oct 6th 2009, 12:05 AM
Bruno J.
Hint : use the Chinese Remainder Theorem.
• Oct 6th 2009, 12:38 AM
jacquelinek
Request more clues
But how?
• Oct 8th 2009, 12:35 AM
kobulingam
Quote:

Originally Posted by jacquelinek
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)

... ... ...