2
$\begingroup$

Problem

Prove that the least quadratic non-residue modulo p is $ \leq \frac{p-1}{4}$

I've been thinking of this problem for 2 days :(, and I'm still not be able to see how to prove it. I also experiment with many data using computer program, the result is patently true, but the pattern is completely vague. A hint would be greatly appreciated.

Thanks,

$\endgroup$
  • $\begingroup$ Is it true form small $p$? $\endgroup$ – Thomas Andrews Apr 16 '11 at 18:36
  • $\begingroup$ @Thomas Andrews: Yes, it is. $\endgroup$ – Chan Apr 16 '11 at 18:53
  • $\begingroup$ Sorry, it's not true for $p=5$ or $p=7,$ since, in those cases, $\frac{p-1}{4}<2$. $\endgroup$ – Thomas Andrews Apr 16 '11 at 18:56
6
$\begingroup$

HINT $\:$ One can easily prove the stronger bound that the least nonsquare $\rm\:a\:$ is less than $\rm\:\sqrt{p}+1\:.\:$ Let $\rm\:b\:$ be least such that $\rm\:ab>p\:,\: $ and let $\rm\:c = ab - p\:$ and consider

$$\rm \bigg(\frac{a}p\bigg)\ \bigg(\frac{b}p\bigg)\ =\ \bigg(\frac{c}p\bigg)$$

Now $\rm\:0 < c < a\ \Rightarrow\ c\:$ is a square, so $\rm\:b\:$ is a nonsquare, so $\rm\ a \le b = (p+c)/a < p/a + 1\:.$

$\endgroup$
3
$\begingroup$

If, for all $a\leq \frac{p-1}{4}$, $a$ is a square mod $p$, that if $b$ is a multiple of $2$ and $\frac{p-1}{4} < b \leq \frac{p-1}{2}$ then $b$ must be a square mod $p$. Similarly, any multiple of $3$ between $\frac{p-1}{2}$ and $\frac{3(p-1)}{4}$ must be a square, and finally any multiple of four in the range $\frac{3(p-1)}{4}$ and $p-1$ must be a square. So that gives us at least:

$$\frac{p-1}{4}(1+ \frac{1}{2} + \frac{1}{3} + \frac{1}{4}) - 4 = \frac{p-1}{2} + \frac{p-1}{24}-4$$

distinct perfect squares, mod $p$. But for $p > 97$, this is more than $\frac{p-1}{2}$.

So, this proof will require that you show by hand for the cases $p\leq 97$ to complete it. That's not hard to do, because if $2$ or $3$ is not a square mod $p$, then you are done, and $2$ is a square mod $p$ if $p \equiv \pm 1 \pmod{8}$ and $3$ is a suqare if $p \equiv \pm 1 \pmod{12}$, so you only really need to check primes $p\equiv \pm 1 \pmod{24}$, so $p=23, 47, 71, 73, 97$. (Actually, you do not need to check $p\equiv 1 \pmod{4}$ because then $-1$ is a square mod $p$, so all of the numbers in the largest quadrent would be squares, as well. This means you only really need to check $p=73$ and $p=97.$ But $5$ is not a quadratic residue for either for either $p$.

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