Prove that if $p$ is an odd prime and $x$ is an integer such that $x^2\equiv 1~mod~p^k$, then $x=\pm 1~mod~p^k$ I'm trying to prove the statement given in the title. I'm quite confused. I would really appreciate if someone can verify, or suggest any changes to what I've got so far.
Assume $x^2 \equiv 1~~mod~~p^k$. Then $p^k$ must divide $x^2-1$, which is equal to $(x-1)(x+1)$. We know that $p^k$ must divide either $(x-1)$or$(x+1)$. Therefore, either $x \equiv 1~~mod~~p^k$ or $x \equiv -1~~mod~~p^k$.
Thank you.
 A: If $p$ is a prime and $p>2$, then $p^k\mid(x-1)(x+1)$ implies $p^k\mid x-1$ or $p^k\mid x+1$, because these two numbers ($x+1$ and $x-1$) cannot have $p$ as a common factor (in that case $p$ would divide the difference, which is equal $2$ - this is impossible for $p>2$).
A: One possible proof is based on the fact that $U(p^k)$ is cyclic.
Indeed, in a cyclic group, there are exactly $\phi(d)$ elements of order $d$ for each $d$ dividing the order of the group.
In particular, in a cyclic group of even order there are exactly two elements such that $x^2=e$: one is $e$ and the other is the single element of order $2$.
Applying all this to $U(p^k)$, we conclude that since $\pm1$ are solutions of $x^2=1$, they are the only solutions.

A simpler solution uses induction on $k$.


*

*$k=1$ is easy.

*$k \to k+1$:
Suppose $x^2 \equiv 1 \bmod p^{k+1}$. Then $x^2 \equiv 1 \bmod p^{k}$ and by induction we have $x \equiv \pm 1 \bmod p^{k}$. Write $x=\pm1 + tp^k$. Then $1 \equiv x^2 \equiv (\pm1 + tp^k)^2 \equiv 1 \pm2tp^k \bmod p^{k+1}$ implies $\pm2tp^k \equiv 0 \bmod p^{k+1}$ and this implies that $p$ divides $t$ and so  $x \equiv \pm 1 \bmod p^{k+1}$.
A: Here is a "MAD PROOF" :
Let $p>2$ a prime number, an integer $k\ge 1$ and $x$ an integer.
To start we have that $p^k \vert (x-1)(x+1)$. We want to say that $p^k\vert (x-1)$ or $p^k\vert(x+1)$. To assume such a statement we need Gauss lemma which means that we must prove that $\gcd(p^k,x-1)=1$ or $\gcd(p^k,x+1)=1$.
To do this the first thing to do is to prove that $\gcd(p,x-1)=1$ or $\gcd(p,x+1)=1$.
Here we go :
We suppose that $p$ does not divide $x$. (Indeed if $p\vert x$ then there exists $j\in\mathbb{Z}$ such that $pj=x \Rightarrow pj\pm 1=x\pm 1$ and with the fact that $p>2$ is a prime number, then $p$ cannot divide $(x\pm 1)$).
By Fermat little theorem we have $x^{p-1}\equiv 1\ [p]\Leftrightarrow x^{p-1}-1\equiv 0\ [p]\Leftrightarrow (x-1)\sum\limits_{k=0}^{p-2}x^k\equiv 0\ [p]$.
By hypothesis $p>2$ is a prime number so by Euclid's lemma $p\vert (x-1)$ or $p\vert\sum\limits_{k=0}^{p-2}x^k$.
In the second case, it means that $p$ does not divide $(x-1)$ and $p>2$ is a prime number so directly $\gcd(p,x-1)=1$.
In the first case, there exists $u\in \mathbb{Z}$ such that $pu=x-1\Rightarrow pu+2=x+1$. And by hypothesis $p$ cannot divide $2$ so $p$ does not divide $(x+1)$. That's why $\gcd(p,x+1)=1$.
Now, with the beautiful properties of $\gcd$ we have $\gcd(p,x-1)=1$ and $p$ which is coprime with $(x-1)$ so $\gcd(p^2,x-1)=\gcd(p,x-1)=1$ (you can see it by multiplying two Bachet-Bézout's identities and by a re-arrangement of the coefficients). We repeat the operation $k-1$ times and obtain $\gcd(p^k,x-1)=\gcd(p,x-1)=1$. Same for $(x+1)$.
We can now apply Gauss lemma and the exercise is done !
