# Correctness of proof of generalized Euler's criterion

My lecture notes on quadratic residues were pretty sloppy, and I was trying to prove some theorems from class. I don't think I'm correct, though. Can anyone tell me if I'm wrong? Specifically, I think Lemma 1 is correct, but the proof for Theorem 1 is incorrect (Theorem 1 is Euler's criterion). • Looks right to me. Is there anything specific you're confused about? – D_S Jun 6 '15 at 0:29
• @D_S I'm pretty sure the proof for Theorem 1 is wrong. It's my hazy recollection of the proof given in class, and frankly I don't understand it. If you do, could you explain me? – Elliot Gorokhovsky Jun 6 '15 at 0:30

You know from Lemma 1 that $b$ is a $k$th power residue if and only if $r$ is divisible by $d := (k, p-1)$. So we just have to show that $d$ divides $r$ if and only if $b^{\frac{p-1}{d}} \equiv 1 \pmod p$.
In any case, $\frac{p-1}{d}$ is always integer, so nothing to worry about there. And by definition, $r$ is a number for which $b \equiv g^r \pmod p$.
First suppose $r$ divides $d$. Then modulo $p$, $$b^{\frac{p-1}{d}} \equiv (g^r)^{\frac{p-1}{d}}$$ Since $r/d$ is an integer, we have $(g^r)^{\frac{p-1}{d}} = (g^{p-1})^{\frac{r}{d}}$. But $g^{p-1} \equiv 1$ by Fermat's little theorem. So you can conclude that $b^{\frac{p-1}{d}} \equiv 1$.
Conversely suppose $b^{\frac{p-1}{d}} \equiv 1$. Again use the fact that $b^{\frac{p-1}{d}} \equiv g^{r \cdot \frac{p-1}{d}}$. You know that if $g^t \equiv 1$, then $p-1$ divides $t$. So $p-1$ has to divide $r \frac{p-1}{d}$, which means that $$\frac{(r \frac{p-1}{d})}{p-1} = \frac{r}{d}$$ is an integer, i.e. $d$ divides $r$.
• Thanks! I was close, but not quite there :). Can this be rewritten without using Fermat's theorem by using cyclic groups? Specifically, $g^{p-1} \equiv 1$ in a cyclic group. – Elliot Gorokhovsky Jun 6 '15 at 2:49