8
$\begingroup$

This is another one of the number theory problems I've been struggling with as of late (hopefully I'm not posting too many questions at once!).

Let $n$ be a positive integer and let $p=2^n+1$ be a prime number. Prove that every quadratic nonresidue modulo $p$ is a primitive root modulo $p$.

Suppose $a$ is a quadratic nonresidue and $r$ a primitive root muodulo $p$. Then there exists no $x$ such that $x^2 \equiv a \mod p$. We must determine the order of $a$. We know that $a$ must be congruent to some power of $r$, say $m$, since $\{r^1,r^2,\ldots,r^{2^n}\}$ is a reduced residue system modulo $p$. Suppose that $\mathrm{ord}_p a=b$. Then $a^b \equiv r^{mb} \equiv 1 \mod p$. We must show that $b=2^n$ since $\phi(p)=2n$. But $r$ is a primitive root and so $mb \equiv 0 \mod{2^n}$ (or $\equiv 2^n \mod{2^n}$). Hence $mb = 2^n k$. How can I finish it?

$\endgroup$
12
$\begingroup$

We will use standard results that you may be familiar with. There are $2^{n-1}$ quadratic non-residues of $p$.

There are $\varphi(\varphi(p))$ primitive roots of $p$. Thus there are $2^{n-1}$ primitive roots of $p$.

It follows that every quadratic non-residue is a primitive root.

$\endgroup$
4
$\begingroup$

If you know the basics of cyclic groups and their subgroups, then the following approach suggests itself.

The group $\Bbb{Z}_p^*$ is cyclic of order $p-1=2^n$. If $a$ is an element of order $2^n$, then it is primitive. OTOH if the order of $a$ is a factor of $2^{n-1}$, then it is a square, because the squares form the unique subgroup of order $2^{n-1}$. By the same argument a squre cannot be primitive.

$\endgroup$
  • $\begingroup$ Wow, this is really neat! +1 $\endgroup$ – Alex Wertheim Nov 19 '13 at 7:33
  • $\begingroup$ A very similar argument works, when $p=2q+1$, with both $p,q$ prime (Sophie Germain prime). An element is $a\in\Bbb{Z}_p^*$ is then a primitive root, iff its order is neither $2$ nor $q$. In the former case $a\equiv-1$, and in the latter case $a$ is a quadratic residue. Both of these possibilities can often be easily excluded. $\endgroup$ – Jyrki Lahtonen Nov 19 '13 at 7:37
3
$\begingroup$

A bit differently: With $r$ a primitive root, we can write $a\equiv r^m$ for some $m$. If $a$ is a quadratic nonresidue, clearly $m$ must be odd. Then $\gcd(m,2^n)=1$ and there exist $u,v\in\mathbb Z$ with $um+v2^n=1$. Thius implies $a^u=r^{um+v2^n}\equiv r$ and hence that $a$ is primitive.

$\endgroup$
0
$\begingroup$

Another approach using Euler’s criterion.

We know, by Euler’s criterion, that if $a$ is a quadratic non-residue, $$a^{(p-1)/2}\equiv -1\pmod p$$ But that would mean $$a^{2^{n-1}}\equiv -1\pmod p\tag 1$$ Since $p=2^n+1$, we have $\phi p=2^n$. So if the order of $p$ is $d$, then $d=2^k$ for some $k\le n$. But $k>n-1$ by (1), so $k=n$, i.e. $a$ is primitive.

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