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, 11: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 6th 2009, 12:05 AMBruno J.
Hint : use the Chinese Remainder Theorem.

- Oct 6th 2009, 12:38 AMjacquelinekRequest more clues
But how?

- Oct 8th 2009, 12:35 AMkobulingam