# Find primitive root mod 17

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

• Easy: in this case, the multiplicative structure is of order $16$, and cyclic as always, thus a $2$-group. Any number that isn’t a quadratic residue will generate. You can easily check that the powers of $3$, for instance, run through all residues. – Lubin May 13 '14 at 19:09
• So any of my QRs will be a primitive root?! :) – sarahusher May 13 '14 at 19:10
• Non-QRs, as I said above. – Lubin May 13 '14 at 19:11
• yes sorry! Okay that's great, thanks! – sarahusher May 13 '14 at 19:13
• how did you calculate the quadtratic residues? – PBJ Apr 29 '17 at 2:40

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$