1
$\begingroup$

Use the primitive root $2$ mod $29$ to find all quadratic residues $a$ mod $29$ with $1 \leq a \leq 28$

I know that primitive roots are integers $x$ whose order is equal to $\varphi(x)$. But, in this question I can't tell if $2$ is the order or if I have to find the order of $2?$

But then how does that relate to finding all quadratic residues? My understanding is that the quadratic residues here would be integers less than $29$ that are perfect squares $\text{mod 29}$. So, an example would be $25$. But I don't recall what kind of relationship there is between primitive roots and perfect squares.

$\endgroup$
0
$\begingroup$

If $g$ is a primitive root mod $p$, then the quadratic residues mod $p$ are exactly $g^{2k}$ for $k=0,\dots,\frac{p-1}{2}$.

One direction is obvious. The other direction is Euler's criterion, which is also easy.

$\endgroup$
  • $\begingroup$ Oh, ok. it looks like i was on a totally "wrong" track altogether. Thank you! But what do you mean by the two directions? You mean directions of the proof for that if $g$ is a primitive root mod $p$ then the quadratic residues mod $p$ are exactly $g^{2k}$ for $k=0,...,\frac{p-1}{2}$? $\endgroup$ – PBJ Apr 29 '17 at 1:41
  • $\begingroup$ @PBJ, yes, directions of the iff proof. $\endgroup$ – lhf Apr 29 '17 at 10:03

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.