# number of square roots of unity modulo a prime power

Let $p\geq 3$ be a prime number and let $k\geq 1$ be some integer.

Is it always true that if $x^2\equiv 1\pmod{p^k}$ then $x\equiv\pm1\pmod{p^k}$ ?

For $k=1$ it is true since $x^2-1\in\mathbb{F}_p[x]$ is a degree $2$ polynomial with two distinct roots $-1,1$ and so any other root in $\mathbb{F}_p$ must be one of them.

I know that there exists a primitive root modulo $p^k$.

• Then you know that you can write each $x\neq 0$ as $g^m$. When is $g^{2m} = 1$? – Daniel Fischer Jul 14 '18 at 20:12
• when $\varphi(p^k)|2m$, so $2m=\ell\varphi(p^k)$ and if $\ell$ is even then $\varphi(p^k)|m$ so $g^m\equiv 1\pmod{p^k}$ but what about odd $\ell$? @DanielFischer – user554578 Jul 14 '18 at 20:19
• You can restrict your attention to $0 \leqslant m < \varphi(p^k)$, then $2m < 2\varphi(p^k)$ and $\varphi(p^k) \mid 2m$ if and only if $2m = 0$ or $2m = \varphi(p^k)$. – Daniel Fischer Jul 14 '18 at 20:24

We know that $$p^k \mid a^2-1=(a-1)(a+1)$$we prove that it is impossible that $$p \mid a-1\\p \mid a+1$$but this is obvious since$$p \mid (a+1)-(a-1)=2$$which is a contradiction for $p>2$ therefore either $p\not\mid a-1$ or $p\not\mid a+1$ which means that either $p \mid a-1$ or $p \mid a+1$
• But this gives us that $a\equiv 1\pmod{p}$ or $a\equiv -1\pmod{p}$ and not necessarily modulo $p^k$. Ah, you say that it must be that $p|a-1$ xor $p|a+1$ and so $p^k|a-1$ xor $p^k|a+1$ ? – user554578 Jul 14 '18 at 20:23
• No. Since $p^k|(a-1)(a+1)$ and $a-1$ and $a+1$ cannot have both common factor $p$ at least one should be coprime with $p$ and the other one must absorb all the power of $p$ say, $p^k$ – Mostafa Ayaz Jul 14 '18 at 20:25
Another way to say that there exists a primitive root modulo $p^k$ is to say that $U(p^k)$ is cyclic. Since it has even order, it has exactly one subgroup of order $2$: the set of all elements such that $x^2=1$.
Another approach using induction (inspired by Hensel’s lemma). Assume $p \neq 2$. For $k=1$ the statement holds. Now if $k > 1$ and $a^2\equiv 1 \pmod{p^k}$ then also $a^2\equiv 1 \pmod {p^{k-1}}$. So by induction $a \equiv \pm 1 \pmod{p^{k-1}}$, that is, $a = \pm 1 + m p^{k-1}$ for some integer $m$. Then $$1 \equiv a^2 = 1 \pm 2 m p^{k-1} + m^2 p^{2k-2}\equiv 1 \pm 2 m p^{k-1} \pmod{p^k}.$$ This means (since $p \neq 2$) that $p \mid m$. Then $a = \pm 1 + m p^{k-1}\equiv \pm 1 \pmod{p^k}$.
We know that $1$ and $-1$ are roots of $1\bmod p^k$.
Let $g$ be a primitive root $\bmod p^k$ and $m:=\phi(p^k)$ be its order. Then considering $(g^i)^2$ with $i\in [1..m]$ we note that only $i=m/2$ and $i=m$ give $(g^i)^2\equiv 1 \bmod p^k$. Thus there are only two roots of $1 \bmod p^k$.