Prove: x = a^(d/2) satisfies x^2 ≡ 1mod(n)

Question

Suppose ordn(a) = d and d is even. Prove: x = a^(d/2) satisfies x^2 ≡ 1mod(n). Does this mean that x ≡ 1 or -1? Explain. I have that x^2 = (a^(d/2))^2 = a^d and by definition of order a^d ≡ 1mod(n) so x^2 ≡ 1mod(n). Now I’m stuck on how to show if x ≡ 1 or -1. From what I understand, it should be both but the question seems to want only one of these. I’ve been reading through my number theory book but I can’t find anything that will let me find out which it is. Is there a theorem that will help me with this?

Answer 1

If $n$ is prime, then indeed $x \equiv \pm 1 \bmod n$.

If $n$ is composite, then we can have $x \not\equiv \pm 1 \bmod n$.

Take for instance $n=15$ and $a=7$. Then $ord(a)=4$ but $a^2 \equiv 4 \bmod n$.