# Legendre Symbol by Fermat's little theorem.

My work:

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

• ty for formatting – hks014 Mar 5 '17 at 9:34
• $g^k\equiv1\mod p\implies p-1$ divides $k$ is false (counter-example: $2^3\equiv1\mod7$). – Bernard Mar 5 '17 at 11:26
• @Bern, you're overlooking that $g$ is to be a generator for the multiplicative group. – Gerry Myerson Mar 5 '17 at 11:35
• It was not in the hypotheses: a generator of $\mathbf Z_p$ is not the same as a generator of $\mathbf Z_p^\times$. – Bernard Mar 5 '17 at 11:39
• @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). – Gerry Myerson Mar 6 '17 at 5:22

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.