Why is $a^{n/2} \equiv -1 \mod p$ but not necessarily -1 modulo a composite? I'm going over a review sheet in preparation for my number theory final. We are asked to prove the following:
|a| = 2r, show that $a^r \equiv -1\mod p$  a prime.
Does this hold modulo n, where n is a composite?
What if |a| = 3r?
Any and all help would be greatly appreciated. I can construct plenty of examples where this breaks down modulo a composite, but can't see why this is so.
 A: A bit of experimenting with GAP or Magma can help here.
In the first case, $a^{r}$ has to be an element of order $2$, If $n$ is not a prime, there can be more elements of order $2$ then just $-1$. For instance when $n = pq$ is the product of two distinct, odd primes, then there are three square roots of $1$ different from $1$.
So for instance take $n = 3 \cdot 5$, $r = 1$, and $a = -1, 4, -4$.
In the second case, $a^{r}$ is an element of order $3$. When $n$ is prime, there are $2$ elements of order $3$ (as $3 r$ divides $p-1$ by assumption), but for instance if $n = 7 \cdot 13$ there are $8$ such elements, namely
$$
9,
16,
22,
29,
53,
74,
79,
81
$$
These facts depend on the CRT.
A: The answer is that $\mathbb{Z}_p^\times$, the group of units modulo $p$, is cyclic of even order (unless $p=2$).  Hence there is exactly one noindentity element whose square is the identity, namely $-1$.
However, $\mathbb{Z}_n^\times$ may not be cyclic, and hence may have multiple elements whose square is the identity.  For example, if $n=8$, $\mathbb{Z}_8^\times\cong 
\mathbb{Z}_2\oplus\mathbb{Z}_2$, and there are three elements whose square is the identity.
