2
$\begingroup$

Question: When $p$ is an odd prime, show that the number of quadratic residues $a$ modulo $p$ with $1\leq a\leq p-1$ is $(p-1)/2$

Answer: From Euler's criterion $\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod{p}$

When we apply Lagrange's theorem, the congruence $a^{(p-1)/2}\equiv 1\pmod{p}$ has at most $(p-1)/2$ solutions

By Fermat's little theorem, we have $a^{p-1}\equiv 1\pmod{p}$, so

$a^{p-1}-1\equiv(a^{(p-1)/2}-1)(a^{(p-1)/2}+1)\equiv 0\pmod{p}$

The answer then says this "has precisely $p-1$ solutions"

How do we deduce from this that this $a^{p-1}-1$ has precisely $p-1$ solutions?

$\endgroup$
3
$\begingroup$

By Fermat's little theorem, $a^{p-1}-1\equiv 0\pmod{p}$ has at least $p-1$ solutions, and since these are solutions to a polynomial over a field of degree $p-1$, it has at most $p-1$ solutions. This gives exactly $p-1$ solutions.

$\endgroup$
  • $\begingroup$ +1 for a nice answer! However, it's not using the argument the O.P. talked about, so you're not answering his precise question. $\endgroup$ – Daniel May 3 '15 at 21:36
  • $\begingroup$ @Solid Snake Oh I was under the impression that the OP was was asking about the last step in the proof. of the statement given in Question. $\endgroup$ – jgon May 3 '15 at 21:38
  • $\begingroup$ Me too, I just noticed he says "How do we deduce from this...", I think he's referring to the equality above. However, I'm not sure now. In any case, your answer is great :) $\endgroup$ – Daniel May 3 '15 at 21:41
  • $\begingroup$ @jgon How does this deduce at least $p-1$ solutions? Is it a standard result that $a^k-1\equiv 0\pmod{p}$ has at least $k$ solutions $\pmod{p}$? $\endgroup$ – Sam Houston May 4 '15 at 9:45
  • $\begingroup$ @Dan smith No, but Fermat's little theorem says that for $1\le a\le p-1$, $a^{p-1}\equiv 1\pmod{p}$. Which is $p-1$ solutions right there. $\endgroup$ – jgon May 4 '15 at 16:26
1
$\begingroup$

Observe that each two of the numbers $1^2,2^2,\dotsc,(\frac{p-1}2)^2$ are non-equivalent modulo $p$ and are quadratic residues.

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