Prove the existence of non trivial solution

Question

The question is

Prove that if an odd integer n > 1 is not a prime or a prime power, then there exists a nontrivial square root of 1 modulo n.

There is a proof "If n is composite, then there exists a non trivial square root of 1 modulo n." I think some prime powers are also composite numbers (eg.16). So how shall I go with the proof?

Thank you

Answer 1

Here's an outline. The function $h(n) = |\{x\in\mathbb{Z}/n\mathbb{Z} : x^2 = 1\}|$ is multiplicative by the Chinese Remainder Theorem. If $p$ is an odd prime, then $h(p^k) = 2$ for all $k\ge 1$, because $1$ and $-1$ are the only roots of unity modulo odd primes.

Now suppose $n$ is odd and not a prime power; let $p$ and $q$ be distinct prime factors of $n$. Then $h(n) \ge h(p)h(q) = 4$, so $\mathbb{Z}/n\mathbb{Z}$ has nontrivial roots of unity.

Answer 2

Hint:

Choose a prime $p$ that divides $n$. Then write $n=p^a\cdot m$ where $p$ does not divide $m$. Then consider the system of congruences: $$\left\{\begin{array}{c} x\equiv 1\pmod{p^a}\\x\equiv -1\pmod{m} \end{array} \right.$$

Answer 3

Suppose $n=pq$ where $p$ and $q$ are coprime.

Then we can find $a,b$ with $ap+bq=1$ and $0\lt|a|\lt q$ and $0\lt|b|\lt p$

Then, modulo $n=pq$ we have $(ap-bq)^2=(ap+bq)^2-4abpq\equiv (ap+bq)^2=1$