3
$\begingroup$

For $m>2$, if a primitive root modulo $m$ exists, prove that the only solutions of the congruence $x^2 \equiv 1 \pmod m$ are $x \equiv 1 \pmod m$ and $x \equiv -1 \pmod m$.

Thanks.

$\endgroup$
0
8
$\begingroup$

Here is an indirect solution - a solution that doesn't use any specific primitive root. I think a better solution exists, but I would still like to post it because it gives a different perspective.

The solutions $1$ and $m-1$ are obviously always solutions. So the difficulty is proving there aren't any more.

By the primitive root theorem, the possibilities for $m$ are $m=2$, $m=4$, $m=p^k$, or $m=2p^k$ where $p$ is an odd prime and $k\ge 1$.

For $m=2$ we actually have $1=m-1$, and there is a unique square root of $1$.

For $m=4$ you may check directly that the claim holds, just by calculating.

For $m=p^k$, we prove by induction on $k$. For $k=1$ there are no zero divisors, so $(x-1)(x+1)=0$ implies $x-1=0$ or $x+1=0$. For $k>1$, assuming there are exactly two solutions modulo $p^{k-1}$, we use Hensel's lemma to claim that these lift to exactly two solutions modulo $p^k$.

For $m=2p^k$ we use the Chinese remainder theorem to combine the two solutions modulo $p^k$ with the unique solution modulo $2$ to get two solutions modulo $m$.

$\endgroup$
0
3
$\begingroup$

Here is a direct solution involving a primitive root (see also my other answer for an "indirect" solution):

Let $r$ be a primitive root modulo $m$ and let $\{r^0, r^1, \ldots, r^s\}$ be the multiplicative group mod $m$.

Let $x$ satisfy $x^2 = 1$. Then $x$ must be a member of the multiplicative group, since it's invertible mod $m$ (it is its own inverse). So we can write $x = r^k$ for some integer $k$, and we know that $r^{2k} \equiv r^0 \pmod m$. This gives us $2k \equiv 0 \pmod {\phi(m)}$ where $\phi$ is Euler's totient function. This congruence has at most two solutions (this I leave as exercise), giving at most two solutions for $x$.

$\endgroup$
1
$\begingroup$

$x^2$$\equiv$1 mod m means that m|($x^2$-1).....what can you infer from this?

$\endgroup$
2
  • 3
    $\begingroup$ If $m$ is not prime, not much. $\endgroup$ Mar 29 '13 at 14:24
  • 1
    $\begingroup$ Yes, but if $m$ has a primitive root, it is 2, 4, $p^k$ or $2 p^k$ for an odd prime $p$. This severely cuts down the options here. $\endgroup$
    – vonbrand
    Mar 29 '13 at 15:43
0
$\begingroup$

Suppose $\,w\,$ is a primitive root modulo $\,m\,$ , and $\,x=w^k\,$ , then

$$x^2=1\pmod m\iff w^{2k}=1\pmod m\iff$$

$$ (w^k-1)(w^k+1)=0\pmod m\iff (x-1)(x+1)=0\pmod m\ldots$$

The fact that any unit $\,x\,$ modulo $\,m\,$ is a power of $\,w\,$ follows from the fact of the latter being a primitive root modulo $\,m\,$...If $\,m\,$ has no primitive roots then the claim isn't true.

Warning: In the last step you still have to give a very little explanation...

$\endgroup$
2
  • $\begingroup$ What is $p$ here? $\endgroup$ Mar 29 '13 at 14:24
  • $\begingroup$ Typo, @YoniRozenshein. Thanks $\endgroup$
    – DonAntonio
    Mar 29 '13 at 14:44
0
$\begingroup$

hint: an equation of degree 2, also in modular arithmetic, has at most two solutions if a primitive root modulo $m$ exists

$\endgroup$
3
  • 3
    $\begingroup$ This is not true because there could be $0$ divisors. For instance $x^2 = 1 \pmod {15}$ has solutions: $x=1$, $x=14$, $x=4$, $x=11$. $\endgroup$ Mar 29 '13 at 13:57
  • 1
    $\begingroup$ No... $x^2 \equiv 1 \pmod{15}$ has solutions $x \equiv 1, 4, 11, 14 \pmod{15}$. You need to use the fact that there is a primitive root $\pmod{n}$. $\endgroup$
    – Ivan Loh
    Mar 29 '13 at 13:58
  • $\begingroup$ After the edit, the answer became a question slightly harder than the original question $\endgroup$ Apr 8 '13 at 8:22

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.