Show that $[-a^2]$ generates Up

57 Views Asked by At

I'm trying to show that $[-a^2]$ generates $U_p$, given that $1<a<p-1$ and p is an odd prime, $p=2q+1$ and q is also an odd prime.

I know that $[-a^2]$ is a primitive root iff 1. $[-a^2]^{\phi(p)/q}\neq[1]$ and 2.$[-a^2]^{\phi(p)/2}\neq[1]$, so I'm trying to prove that 1&2 holds. Am I going in the right direction? 2 is easy to show, since $[-a^{2q}]=[-1]\neq[1]$. But how do I prove 1, i.e. $[a^4]\neq1$?

1

There are 1 best solutions below

2
On BEST ANSWER

You are very much on the right track, and in a comment at the end we answer your specific question. But for fun we prove the result using a counting argument. The number of primitive roots of $p$ is $\varphi(p-1)$. But $p-1=2q$, and $\varphi(2q)=q-1$.

So the number of primitive roots of $p$ is $q-1$, which is $\frac{p-1}{2}-1$. The number of quadratic non-residues of $p$ is $\frac{p-1}{2}$. It follows that every quadratic non-residue of $p$ except for one is a primitive root of $p$.

Note that $p$ is of the form $4k+3$, so $-1$ is a quadratic non-residue of $p$. It is obviously not a primitive root of $p$, since it has order $2$.

Finally, we observe that $-a^2$ is not congruent to $-1$, for it it were, we would have $a^2\equiv 1\pmod{p}$, that is, $a=1$ or $a=p-1$, and these are excluded in the statement of the problem.

Remark: To show that we cannot have $a^4\equiv 1\pmod{p}$, we observe that if $a^4\equiv 1\pmod{p}$ then $a^2\equiv 1\pmod{p}$ or $a^2\equiv -1\pmod{p}$. The congruence $a^2\equiv 1\pmod{p}$ has the two solutions $a\equiv \pm 1$, and these are excluded in the problem. And $a^2\equiv -1\pmod{p}$ is impossible, since $p$ is of the form $4k+3$.