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.

Printable View

- Oct 5th 2009, 10:35 PMjacquelineksquare 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 5th 2009, 11:05 PMBruno J.
Hint : use the Chinese Remainder Theorem.

- Oct 5th 2009, 11:38 PMjacquelinekRequest more clues
But how?

- Oct 7th 2009, 11:35 PMkobulingam