Why is $a^{n/2} \equiv -1 \mod p$ but not necessarily -1 modulo a composite?

Question

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.

Answer 1

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.

Answer 2

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.