I have to list the quadratic residues of $17$ and find a primitive root. I have calculated that:
Quadratic residues $mod(17)$ are $1,2,4,8,9,13,15,16$
How am I then meant to use this to obtain a primitive root of $17$?
Thank you
$\endgroup$ 51 Answer
$\begingroup$In the case of $p=17$, if $a$ is a quadratic residue $\mod 17$, then $a^8=1\mod 17$, so $a$ can't be a primitive root $\mod 17$. However, if $a$ is a quadratic non-residue $\mod 17$, then $a^8=-1\mod 17$, and therefore the order of $a%$ is $16$, implying $a$ is a primitive roots $\mod 17$. So the primitive roots $\mod 17$ are equivalent to the quadratic non-residues $\mod 17$: ${3, 5, 6, 7, 10, 11, 12, 14}$. This is not true in general however. In fact, if the primitive roots $\mod p$ are the quadratic non-residues $\mod p$ excluding $-1$, then $p$ is a Fermat prime ($p=2^{2^n}+1$), or $p$ is a Sophie Germain prime ($p=2n+1$ where $n$ is prime).
If $a$ is a primitive root $\mod p$, then
$a^{p-1}=1\mod p$
and for all primes $q$ dividing $p-1$
$a^{(p-1)/q}≠1\mod p$
$\endgroup$
