0
$\begingroup$

Question:

Show that if $g$ is a primitive root modulus $p$ for an odd prime $p$, then $g$ has no square root modulus $p$ (i.e., $x^2 \equiv g \bmod p$ has no solution)

Sample solution of textbook:

Suppose that $x^2 \equiv g \bmod p$. Then $g^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \bmod p$ (by Fermat), contradicting $g$ being a primitive root.

However, sample solution does not make sense. In fact,

$g^{\frac{p-1}{2}} \equiv -1 \bmod p$

$x^{p-1} \equiv 1 \bmod p$

Hence, $g^{\frac{p-1}{2}} \not\equiv x^{p-1} \bmod p$

Am I correct?

$\endgroup$
3
  • $\begingroup$ That's exactly the contradiction that the solution is getting at $\endgroup$
    – TomGrubb
    Commented Dec 18, 2016 at 1:59
  • $\begingroup$ @bburGsamohT I don't understand, can you explain more. $\endgroup$
    – Node.JS
    Commented Dec 18, 2016 at 2:00
  • $\begingroup$ After you assume something false (at the start of a proof by contradiction) it is possible to conclude the proof by many different absurdities. You have simply found a slightly different path to a contradiction. $\endgroup$ Commented Dec 18, 2016 at 2:06

1 Answer 1

1
$\begingroup$

The sample solution doesn't rely on any intermediate value of $g^k$ before $k$ reaches $p\mathord-1$, only that $k=p\mathord-1$ is the smallest value of $k>0$ that has $g^k\equiv 1 \bmod p$. That's the contradiction elicited by showing that, since $x^{p\mathord-1}\equiv 1$ and thus $(x^2)^{(p\mathord-1)/2}\equiv 1$ also, there cannot be a $g\equiv x^2$ for a primitive root $g$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .