2
$\begingroup$

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).

enter image description here

$\endgroup$
  • $\begingroup$ Looks right to me. Is there anything specific you're confused about? $\endgroup$ – D_S Jun 6 '15 at 0:29
  • $\begingroup$ @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? $\endgroup$ – Elliot Gorokhovsky Jun 6 '15 at 0:30
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Elliot Gorokhovsky Jun 6 '15 at 2:49
  • $\begingroup$ Actually, never mind, that doesn't matter, it's a trivial substitution. $\endgroup$ – Elliot Gorokhovsky Jun 6 '15 at 3:46

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.