4
$\begingroup$

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$
  • 1
    $\begingroup$ 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. $\endgroup$ – Lubin May 13 '14 at 19:09
  • $\begingroup$ So any of my QRs will be a primitive root?! :) $\endgroup$ – sarahusher May 13 '14 at 19:10
  • $\begingroup$ Non-QRs, as I said above. $\endgroup$ – Lubin May 13 '14 at 19:11
  • $\begingroup$ yes sorry! Okay that's great, thanks! $\endgroup$ – sarahusher May 13 '14 at 19:13
  • $\begingroup$ how did you calculate the quadtratic residues? $\endgroup$ – PBJ Apr 29 '17 at 2:40
6
$\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$

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.