6
$\begingroup$

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!!)


  • 2
    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?2011-03-27
  • 0
    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.2011-03-27
  • 0
    @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?2011-03-27
  • 0
    @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.2011-03-27
  • 0
    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?2011-03-27
  • 0
    @DJC: Yes, that does it. Or, a group exponent 2 must be a direct sum of copies of $C_2$, and the only cyclic one is the one of two elements. This argument avoids Hensel's Lemma, but uses the existence of primitive roots (which is a pretty strong theorem itself!) user6312's argument is much more elementary. Or: $p$ divides at most one of $x-1$ and $x+1$, so if $p^{\ell}$ divides the product, it must divide one of the factors since the other one is prime to $p$.2011-03-27
  • 0
    @Arturo. Thanks for your help. What is $C_2$? Do you mind writing your second comment as an answer? I am also interested in solving the case $x^2 \equiv t \pmod{p^{\ell}}$, where $t$ is a unit. This argument seems not to carry over to this case as $\{x | x^2 \equiv t\}$ is no longer a subgroup. Is this argument reparable or is Hensel's Lemma a "better" way?2011-03-27
  • 0
    @DJC: $C_2$ is the cyclic group of order $2$. As for my second comment, it's user6312's answer, so you should accept *that*. Both arguments for $x^2\equiv t$ work by reducing to the previous case. If there is at least one solution $a$, find $b$ with $ab\equiv1\pmod{p^{\ell}}$. Any solution $r$ to $x^2\equiv t$ will have $(rb)^2 \equiv tb^2 \equiv a^2b^2 \equiv 1\pmod{p^{\ell}}$, and any solution $s$ to $x^2\equiv 1$ gives $sa$ for a solution to $x^2\equiv t$. So there is a correspondence between solutions to $x^2\equiv t$ and solutions to $x^2\equiv 1$.2011-03-27
  • 0
    @Arturo, Thank you again for your help!2011-03-27

2 Answers 2

8

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.)

  • 0
    How do you know (x-1)(x+1) is the only factorization?2011-03-27
  • 5
    We do not need to know that for the argument. We only need to know that it is a factorization.2011-03-27
  • 2
    Well, what if $p^{l-2}$ divides $x-1$ and $p^2$ divides $x+1$?2011-03-27
  • 0
    @Numth: Then $p$ divides $2$.2011-03-27
  • 2
    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$.2011-03-27
  • 0
    @Numth: It starts with the observation that $p$ itself divides at most one of $x-1$ and $x+1$. So at least one of $x-1$ and $x+1$ is *prime to* $p$, not merely not divisible by $p^{\ell}$.2011-03-27
  • 0
    Yes. That is my point. There's more to just that $p^l$ doesn't divide both of them.2011-03-27
  • 0
    @user6312. After putting the problem down and now revisiting it, I appreciate the elementariness of your argument!2011-03-28
6

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\:.$