Nontrivial square root of 1 modulo n example
Answers
Answered by
0
If n is composite, but has more than 1 prime factor, then there typically exist nontrivial square roots. Let n=PQn=PQ, where P and Q are coprime and greater than 1. Then the system x≡1modP,x≡−1modQx≡1modP,x≡−1modQ has a solution for xx by the Chinese remainder theorem, x2≡1modnx2≡1modn. As long as we can choose P,QP,Q not equal to 2, x≠±1modnx≠±1modn. That can be done as long as n is not twice a prime. That leaves us with powers of primes.
Let n=pkn=pk. Then a square root of 1 modulo n satisfies (x−1)(x+1)≡0modn(x−1)(x+1)≡0modn, in particular n must divide (x−1)(x+1)(x−1)(x+1). We note the difference of these two factors is 2, so any common factor of these two terms must also be a factor of 2. In particular, if pp is odd, then all the powers of pp must be factors of one term only, and we end up with only the trivial roots. So the converse isn't true if nn is a power of an odd prime.
Finally that leaves n=2kn=2k, and perhaps as expected, 2 behaves somewhat differently. We already showed there are only two square roots of 1 modulo 4, but it turns out that all the odd residues modulo 8 have squares equal to 1. In general, for n=2kn=2k, we find x=2k−1±1x=2k−1±1 also satisfy x2≡1modnx2≡1modn.
So the final solution is - there exists nontrivial square roots for composite nn except for two cases: nn is a power of an odd prime, or if nn is twice a prime.
Let n=pkn=pk. Then a square root of 1 modulo n satisfies (x−1)(x+1)≡0modn(x−1)(x+1)≡0modn, in particular n must divide (x−1)(x+1)(x−1)(x+1). We note the difference of these two factors is 2, so any common factor of these two terms must also be a factor of 2. In particular, if pp is odd, then all the powers of pp must be factors of one term only, and we end up with only the trivial roots. So the converse isn't true if nn is a power of an odd prime.
Finally that leaves n=2kn=2k, and perhaps as expected, 2 behaves somewhat differently. We already showed there are only two square roots of 1 modulo 4, but it turns out that all the odd residues modulo 8 have squares equal to 1. In general, for n=2kn=2k, we find x=2k−1±1x=2k−1±1 also satisfy x2≡1modnx2≡1modn.
So the final solution is - there exists nontrivial square roots for composite nn except for two cases: nn is a power of an odd prime, or if nn is twice a prime.
Similar questions