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?
 A: Outline for an answer.
Let $g(m)$ be the number of distinct roots to $x^2\equiv1\pmod m.$
If $m,n$ are relatively prime, then show $g(mn)=g(m)g(n).$ (Hint: use Chinese remainder theorem.) (This property is called being “multiplicative.”)
This is true for any polynomial congruence in one variable. If $h(m)$ is the number of solutions to $x^3+x\equiv 1\pmod m,$ then $h$ is multiplicative.

So we only need to comoute $g(p^k),$ where $p$ is a prime.
If $p$ is an odd prime, then show $g(p^k)=2$ for any $k>0.$
This is because $x^2\equiv 1\pmod {p^k},$ means $p^k\mid x^2-1=(x-1)(x+1).$ But $x-1$ and $x+1$ cannot both be divisible by $p,$ so this means $p^k\mid x-1$ or $p^k\mid +1,$ and thus $x\equiv\pm 1\pmod{p^k}.$
If $p=2,$ you have the problem that $x-1$ and $x+1$ can both be divisible by $2.$
Show that:
$$g(2^k)=\begin{cases}1&k=0,1\\2&k=2\\4&k>2 \end{cases}$$

Finally, if $$m=2^kp_1^{k_1}p_2^{k_2}\cdots p_{n}^{k_n}$$ with the $p_i$ distinct odd primes, then:
$$g(m)=g(2^k)2^n$$
A: Ok. Do you know that if and only if $m$ ist prime then $\mathbb Z/m\mathbb Z$ is a field?
A polynomial of degree $n$ over a field has at most $n$ roots in that field. So the polynomial $x^2-1$ can have no roots or $2$ roots (it cannot be that is has only $1$ root, as this would imply by factoring that it does in fact have two roots).
In our case it is clear, the two roots are $1$ and $-1=m-1$.
Now, if $m=2,4,p^k,2p^k$ for an odd prime $p$, then $(\mathbb Z / m\mathbb Z)^\times$ is cyclic, e.g. each element is of the form $g^l$ for some generator $g$. Then $g^{2l}$ hits only half of the elements, but each one twice (except for $m=2$, were the multiplicative group only has one element).
Thus also in this case we only get $1$ and $-1$.
If $m=2^k$, then any root has to be a root modulo $2$, so any root has to be of the form $1+2l$. Then
$$ (1+2l)^2 - 1 = 1 + 4l^2 + 4l - 1 = 4l(l+1) $$
this can only be $0$ modulo $2^k$ if either $l$ or $(l+1)$ is a multiple of $2^{k-2}$. Since we only need to consider $0\leq l < 2^k$ we only get these possibilities: $0$, $2^{k-2}$, $2^{k-1}$, $3\cdot 2^{k-2}$.
Note that if $l=2^{k-1}$ or $2^{k-1}-1$ then $2l \equiv 2\cdot0$ or $2l\equiv 2\cdot(0-1)$. So we only have to count the cases $0$ and $2^{k-2}$ for $l$ or $l+1$. This gives us exactly four solutions $1,-1,1+2^{k-1},-1+2^{k-1}$ if $k>2$ (else we only get 2 solutions for $k=2$ and one solution for $k=0$).
So now we can handle the cases of all prime powers. So if $m$ is composite, we can use the CRT to get all roots modulo $m$ by getting all those modulo the prime powers.
So if $m=2^k p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$ for odd prime numbers $p_i$ then we have to use the CRT to find $x$ that satisfies:
$$ x\equiv \pm 1\mod p_i^{k_i}$$
and if $k>0$ one of these
$$ x\equiv 1 \mod 2\qquad \text{if $k=1$} $$
$$ x\equiv \pm 1\mod4 \qquad \text{if $k=2$} $$
$$ x\equiv \pm 1 + \{0,2^{k-1}\} $$
for all such combinations. By the CRT each such combination corresponds to a unique root modulo $m$, so we get a total of $2^n$ roots if $k=0,1$, $2^{n+1}$ roots if $k=2$ and $2^{n+2}$ roots if $k>2$.
A: 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$.
