<s>[INST] Let $z \in \Bbb Z_m$, when is $z^2 \equiv 1$? Let $z \in \Bbb Z_m$. When is $z^2=1, (z\neq1)$?
I know that for $m$ prime, $z=p-1$ is it's own inverse, but what about nonprime $m$?
Is $p-1$ the only self inverse element in $\Bbb Z_p$ ?
 [/INST] Let $p$ be an odd prime throughout.
Claim 1: In $\mathbb{Z}/p\mathbb{Z}$, the only numbers $n$ such that $n^2 \equiv 1$ are $\pm 1$.
Proof. Suppose $n$ is such that $n^2 \equiv 1 \pmod p$. Then we must have that $p \mid n^2 - 1 = (n+1)(n-1)$. Since $p$ is prime, we know that we then have $p \mid n+1$ or $p \mid n-1$. In the first case, we have that $n \equiv -1 \pmod p$, and in the second case we have that $n \equiv 1 \pmod p$. So we've proven the claim. $\clubsuit$
Claim 2: In $\mathbb{Z}/p^n\mathbb{Z}$, the only numbers $n$ such that $n^2 \equiv 1$ are $\pm 1$.
Proof. This is not actually conceptually any different, but I present this separately. Suppose $n$ is such that $n^2 \equiv 1 \pmod {p^n}$. The in particular $p^n \mid n^2 - 1 = (n+1)(n-1)$ as above. And in particular, $p \mid (n+1)(n-1)$, so that either $p \mid n+1$ or $p \mid n-1$. Since $p > 2$, we cannot have that $p$ divides both, so $p$ divides exactly one of $n+1$ or $n-1$. Thus $p^n$ divides exactly one of $n+1$ or $n-1$. In the former case, we have that $n \equiv -1 \pmod {p^n}$. In the latter, $n \equiv 1 \pmod {p^n}$. So we've proven the claim. $\clubsuit$
Claim 3: In $\mathbb{Z}/2\mathbb{Z}$ and $\mathbb{Z}/4\mathbb{Z}$, there are $1$ and $2$ solutions to $x^2 \equiv 1$, respectively.
Proof. You can simply do it, checking manually. $\spadesuit$
Claim 4: In $\mathbb{Z}/2^n\mathbb{Z}$ for $n \geq 3$, there are exactly $4$ solutions to $x^2 \equiv 1$. They are given by $x \equiv \pm 1 \pmod {2^{n-1}}$.
Proof. This is similar to the above proofs, but slightly more annoying. Again suppose that $x$ satisfies $x^2 \equiv 1 \pmod {2^n}$. Then $2^n \mid (x+1)(x-1)$. But since the difference between $x+1$ and $x-1$ is $2$, we will have that one will be divisible by $2$ and the other divisible by $2^{n-1}$ (note that they cannot both be divisible by $4$ for instance). If $2^{n-1} \mid x+1$, then we have that $x \equiv -1 \pmod{2^{n-1}}$. If $2^{n-1} \mid x-1$, then we have that $x \equiv 1 \pmod{2^{n-1}}$. When raised to $2^n$, these give the $4$ solutions mod $2^n$. $\clubsuit$
We now appeal to the Chinese Remainder Theorem to patch together different congruences mod different primes. In particular, we get $2$ choices of congruence class per odd prime and either $1, 2,$ or $4$ choices for powers of $2$. So if $n = 2^{a_0} p_1^{a_1} \ldots p_k^{a_k}$, then we have $2^k \cdot T(a_0)$ choices of congruences classes from the Chinese Remainder Theorem, where $T(0) = T(1) = 1, T(2) = 2$, and $T(a) = 4$ for $a \geq 3$.
And so this is the number of square roots of $1$ mod $n$. $\diamondsuit$
</s>