0
$\begingroup$

Question

My work:

enter image description here

How do continue with part $b$, I'm so confused.

$\endgroup$
  • $\begingroup$ ty for formatting $\endgroup$ – hks014 Mar 5 '17 at 9:34
  • $\begingroup$ $g^k\equiv1\mod p\implies p-1$ divides $k$ is false (counter-example: $2^3\equiv1\mod7$). $\endgroup$ – Bernard Mar 5 '17 at 11:26
  • $\begingroup$ @Bern, you're overlooking that $g$ is to be a generator for the multiplicative group. $\endgroup$ – Gerry Myerson Mar 5 '17 at 11:35
  • $\begingroup$ It was not in the hypotheses: a generator of $\mathbf Z_p$ is not the same as a generator of $\mathbf Z_p^\times$. $\endgroup$ – Bernard Mar 5 '17 at 11:39
  • $\begingroup$ @Bern, I think it's clear from the context that we're talking about multiplication, not addition. After all, additively, 1 is a generator, but $g=1$ makes no sense at all in (c). $\endgroup$ – Gerry Myerson Mar 6 '17 at 5:22
0
$\begingroup$

All elements of $\mathbf Z_p^\times$ satisfy the equation $x^{p-1}=(x^q)^2\equiv=1\mod p,\;$ i.e. $\;x^q\equiv 1$ or $x^q\equiv-1$. Now, all squares satisfy $x^q\equiv1$ by Lil' Fermat, and there are $q$ of them.As there can't be more than $q$ solutions to this equation, any element $c$ satisfying $c^q\equiv 1$ is a square.

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