4
$\begingroup$

if $m$ is an integer greater than 2, and a primitive root modulo $m$ exists, prove that the only incongruent solutions of $x^2 \equiv 1 \mod m$ are $x \equiv \pm 1 \mod m$.

I know that if a primitive root mod $m$ exists, then $m = 1, 2, 4, p^m,$ or $2p^m$, where p is an odd prime and $m$ is a positive integer. Obviously I can check the cases where $m = 1, 2, 4$ by hand but I am having trouble proving the other two cases.

$\endgroup$
1
$\begingroup$

$1,2,4$ can be dealt easily.

For $p^m$ divides $(x^2-1)=(x-1)(x+1)$

Now, $x+1-(x-1)=2\implies (x-1,x+1)$ divides $2$

So, either $p^m$ divides $(x-1)$ or $(x+1)$ resulting in exactly $2$ in-congruent solutions

If $2\cdot p^m$ divides $(x^2-1)=(x-1)(x+1)$

Clearly, $x$ is odd

So, $p^m$ divides $\frac{x-1}2\cdot\frac{x+1}2$

Now, $-\frac{x-1}2+\frac{x+1}2=1\implies (\frac{x+1}2,\frac{x-1}2)=1$

So, either $p^m$ divides $\frac{x-1}2$ or $\frac{x+1}2$ resulting in exactly $2$ in-congruent solutions


Alternatively, f $x^d\equiv1\pmod m$ and $m$ has a primitive root $a$

Taking Discrete logarithm, $d\cdot ind_ax\equiv ind_a1\pmod {\phi(m)}\equiv0$

Using Linear congruence theorem, it has exactly $(d,\phi(m))$ solutions as $(d,\phi(m))$ divides $0$

$\endgroup$
1
$\begingroup$

Hint $\ $ If $\rm\:g\:$ generates a cyclic group of order $\rm\:2n,\:$ and $\rm\:x = g^k,\:$ then

$$\rm 1 = x^2\! = g^{2k}\!\!\iff 2n\mid 2k\iff n\mid k\iff x\! = g^n\, \ or\, \ x = g^0\! = 1$$

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