2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Then you know that you can write each $x\neq 0$ as $g^m$. When is $g^{2m} = 1$? $\endgroup$ – Daniel Fischer Jul 14 '18 at 20:12
  • $\begingroup$ 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 $\endgroup$ – user554578 Jul 14 '18 at 20:19
  • $\begingroup$ 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)$. $\endgroup$ – Daniel Fischer Jul 14 '18 at 20:24
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – user554578 Jul 14 '18 at 20:23
  • $\begingroup$ 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$ $\endgroup$ – Mostafa Ayaz Jul 14 '18 at 20:25
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.