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,

  • 0
    Sorry, it's not true for $p=5$ or $p=7,$ since, in those cases, \frac{p-1}{4}<2.2011-04-16

2 Answers 2

6

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

3

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