# Solving $x^2 \equiv 1 \pmod{p^{\ell}}$

I am working through Ireland/Rosen at the moment, and I cannot solve a (probably) simple exercise. Any nudges you can give me in the right direction are appreciated.

How does one show that $x^2 \equiv 1 \pmod{p^{\ell}}$ has only two solutions (namely $\pm 1$)? Here, $\ell$ is a positive integer (which we can take to be at least $2$ as $\mathbb{F}_p$ is a field and must therefore only have two solutions).

I am aware of how to prove this statement in general using Hensel's Lemma, but there must be an elementary (maybe two line) proof as it is in the first few chapters of Ireland/Rosen. The book also discusses Euler's theorem around this point:

$$x^{\varphi(n)} \equiv 1 \pmod{n},$$

where $\varphi(n)$ is the totient function, and I suspect this plays a role.

How does one show that $x^2 = 1 \pmod{p^{\ell}}$ has only two solutions, without invoking Hensel's lemma? (Please provide hints only!!)

-
Do you already know that there is a primitive root modulo $p^{\ell}$ for any $\ell$ (when $p$ is odd, at any rate)? Or, equivalently, that the group of units modulo $p^n$ is cyclic? – Arturo Magidin Mar 27 '11 at 19:15
I am aware that the units mod $p^{\ell}$ form a cyclic group, but I have not thought about the equivalent statement concerning primitive roots. – JavaMan Mar 27 '11 at 19:22
@DJC: If you already know that the units form a cyclic group, then consider the subset $\{x\mid x^2\equiv 1\}$; show it is a subgroup. What do groups of exponent $2$ look like? What do subgroups of cyclic groups look like? – Arturo Magidin Mar 27 '11 at 19:24
@DJC: As for primitive roots: $g$ is a primitive root modulo $n$ if and only if every number relatively prime to $n$ is congruent to some power of $g$; that is, if and only if the class of $g$ generates the multiplicative group of units; that is, a primitive root exists if and only if the group of units is cyclic. – Arturo Magidin Mar 27 '11 at 19:25
I see. Since $S = \{x | x^2 \equiv 1\}$ is a subgroup of a cyclic group, it itself is cyclic. Therefore, it is generated by some element $g$, and $S = \{g, g^2, \dots,g^k\}$. Since $g^2 \equiv 1$, we must have $S = \{g, 1\}$. Finally, since $-1 \in S$, we must actually have $g = -1$. Is this basically the argument? – JavaMan Mar 27 '11 at 19:48

## 2 Answers

Let $p$ be an odd prime. Then $p^{\ell}$ can divide at most one of $x-1$ and $x+1$. (Note that the argument breaks down if $p=2$, and indeed in that case there can be more than 2 solutions.)

-
How do you know (x-1)(x+1) is the only factorization? – Graphth Mar 27 '11 at 19:33
We do not need to know that for the argument. We only need to know that it is a factorization. – André Nicolas Mar 27 '11 at 19:43
Well, what if $p^{l-2}$ divides $x-1$ and $p^2$ divides $x+1$? – Graphth Mar 27 '11 at 20:06
@Numth: Then $p$ divides $2$. – Chris Eagle Mar 27 '11 at 20:23
Yes, I know. I'm not asking for my sake. I'm just saying the original answer would be a little clearer to start with $p$ can divide at most one of $x-1$ and $x+1$. It's not a huge deal obviously. But, it adds an extra step to start with $p^l$. – Graphth Mar 27 '11 at 20:35

HINT $\rm\ \ \ p\:$ prime, $\rm\ \ (p,a,b)\ =\ 1,\ \ \ p^n\ |\ a\:b\ \ \Rightarrow\ \ p^n\ |\ a\$ or $\rm\ p^n\ |\ b\ \$ by iterating Euclid's Lemma.

Note that $\rm\ \ (p,x-1,x+1)\ =\ (p,x-1,x+1-(x-1))\ =\ (p,x-1,2) = 1\$ for odd $\rm\:p\:.$

I.e. if $\rm\:p^n\:$ divides a product of pairwise $\rm\:p\:$-coprime elements $\rm\:a_i\:$ then $\rm\:p^n\:$ divides one of the $\rm\:a_i\:,\:$ for otherwise, by unique factorization, $\rm\ p\:$ divides at least two factors $\rm\:a_i,\ a_j\:$ contra $\rm\ (p,\:a_i,\:a_j)\ =\ 1\:.$

-