<s>[INST] square root of $1 \pmod m$ for prime $m$ and non prime $m$ While doing square root $1$ moduli i.e. $x ^2 \equiv 1 \pmod m$ I noticed the following:
If the moduli $m$ is prime it seems that the square is always $1$ and $m - 1$
But if it is not prime, it is not the case and I am not sure if there is a general formula for that.
Examples:
$1 \pmod 3$: $1$ and $2$
$1 \pmod 4$: $1$ and $3$
$1 \pmod 5$: $1$ and $4$
$1 \pmod 6$: $1$ and $5$
$1 \pmod 7$: $1$ and $6$
$1 \pmod 8$: $1$ and $3$ and $5$ and $7$
$1 \pmod 9$: $1$ and $8$
$1 \pmod {11}$: $1$ and $10$
Here we see that for prime modulo we have $1$ and $m - 1$ while for non prime it varies.
Am I right to generalize that for prime it always holds? What is the property that causes this and is there a general conclusion for non prime?
 [/INST] If $a$ and $b$ are two coprime positive integers and
$$x_1^2\equiv1\pmod{a}\qquad\text{ and }\qquad x_2^2\equiv1\pmod{b},\tag{1}$$
then by the Chinese remainder theorem there exists a unique integer $x$ with $0\leq x<ab$ such that
$$x\equiv x_1\pmod{ab}\qquad\text{ and }\qquad x\equiv x_2\pmod{ab},$$
which consequently satisfies $x^2\equiv1\pmod{a}$ and $x^2\equiv1\pmod{b}$, and hence
$$x^2\equiv1\pmod{ab}.\tag{2}$$
This shows that the solutions to $(2)$ correspond bijectively to pairs of solutions to $(1)$. So if $N(m)$ is the number of solutions to $x^2\equiv1\pmod{m}$, then $N(ab)=N(a)N(b)$. It follows that if $m$ is a positive integer which factors as $m=\prod p^{m_p}$, then
$$N(m)=\prod N(p^{m_p}).$$
So it suffices to determine the number of solutions for all prime powers.

If $m=p$ is prime and $x^2\equiv1\pmod{p}$ then $p$ divides
$$x^2-1=(x-1)(x+1),$$
and so either $p$ divides $x-1$ or $p$ divides $x+1$, or equivalently, for some integer $n$ we have
$$x=np\pm1.$$
If we require that $0\leq x<p$ then the only solutions are $x=1$ and $x=m-1$. Note that these are not distinct only for $p=2$.

Similarly, if $m=p^k$ is an odd prime power and $x^2\equiv1\pmod{p^k}$ then $p^k$ divides
$$x^2-1=(x-1)(x+1).$$
Because the two factors differ by $2$ they cannot both be divisible by $p$, and so either $p^k$ divides $x-1$ or $p^k$ divides $x+1$, or equivalently, for some integer $n$ we have
$$x=np^k\pm1.$$
If we again require that $0\leq x<p^k$ then the only solutions are $x=1$ and $x=m-1$, and so $N(p^k)=2$.

On the other hand, if $m=2^k$ and $x^2\equiv1\pmod{2^k}$ then $2^k$ divides
$$x^2-1=(x-1)(x+1).$$
Because the two factors differ by $2$ they must both be even, and they cannot both be divisibly by $4$, and so either $2^{k-1}$ divides $x-1$ or $2^{k-1}$ divides $x+1$, or equivalently, for some integer $n$ we have
$$x=n2^{k-1}\pm1.$$
If we again require that $0\leq x<2^k$ then the only solutions are
$$x=1,\qquad x=2^{k-1}-1,\qquad x=2^{k-1}+1,\qquad x=2^k-1.$$
Note that for $k=1$ and $k=2$, corresponding to $m=2$ and $m=4$, this only yields $1$ and $2$ distinct solutions, respectively. This shows that $N(2)=1$, $N(4)=2$ and $N(2^k)=4$ for $k\geq3$.
</s>