# On primes which have 5 as a quadratic residue

Well, for which primes $p$ is $5$ a quadratic residue?

I went about it this way:

Let $p' = \frac{p-1}{2}$.

Now, from Gauss' Lemma for Quadratic Congruences, $\displaystyle\left(\frac{5}{p}\right) = (-1)^S$, where $S= \displaystyle \sum_{i=1}^{p'}\lfloor{\frac{10i}{p}} \rfloor$, and where the $\left(\frac{x}{y}\right)$ is the legendre symbol.

Then, we note that $\lfloor \frac{10i}{p} \rfloor = 0$, from $1 \le i \le \lfloor \frac{1}{5} p' \rfloor$. Further,

$\lfloor \frac{10i}{p} \rfloor = 1$, from $\lfloor \frac{1}{5} p' \rfloor < i \le \lfloor \frac{2}{5} p' \rfloor$,

$\lfloor \frac{10i}{p} \rfloor = 2$, from $\lfloor \frac{2}{5} p' \rfloor < i \le \lfloor \frac{3}{5} p' \rfloor$, and so forth.

Now, we're primarily concerned with,

$S= \displaystyle \sum_{i=1}^{p'}\lfloor{\frac{10i}{p}} \rfloor\ mod \ 2 \equiv \lfloor \frac{4}{5} p' \rfloor- \lfloor \frac{3}{5} p' \rfloor + \lfloor \frac{2}{5} p' \rfloor - \lfloor \frac{1}{5} p' \rfloor$.

We get this last expression, by noting that we only get odd values in the intervals $\lfloor \frac{3}{5} p' \rfloor < i \le \lfloor \frac{4}{5} p' \rfloor$ and $\lfloor \frac{1}{5} p' \rfloor < i \le \lfloor \frac{2}{5} p' \rfloor$.

Okay, now my question essentially lies in how to simplify this final expression of floor functions. How do I do this? Because after that, I can simply look at the conditions required on p for that final expression to be even, in which case $\displaystyle \left(\frac{5}{p}\right) =1$, and 5 to be a quadratic residue.

A further question, if possible, how do I develop some intuition for how to add and subtract floor functions? Is there anything I can read for this?

Thank You!

-
Are you only interested in answers that do it your way, or would you also be interested in answers that use quadratic reciprocity? –  Zev Chonoles Jul 28 '13 at 15:16
@ZevChonoles Well, that would be great, thanks. Nevertheless, it would be nice to see whether or not I was just heading down a blind alley, and perhaps also learn something about arithmetic using the floor functions. –  AlpArslan Jul 28 '13 at 18:38

Note that $$f(p')=\lfloor \frac{4}{5} p' \rfloor- \lfloor \frac{3}{5} p' \rfloor + \lfloor \frac{2}{5} p' \rfloor - \lfloor \frac{1}{5} p' \rfloor$$

Is periodic in $5$ under the integers modulo $2$, $$f(m+5)\equiv f(m) \text{ mod 2}$$

Thus we get in the integers modulo $2$:

$$f(m)=0, \text{if } m\equiv 0 \text{ mod 5}$$

$$f(m)=0, \text{if } m\equiv 1 \text{ mod 5}$$

$$f(m)=0, \text{if } m\equiv 2 \text{ mod 5}$$

$$f(m)=0, \text{if } m\equiv 3 \text{ mod 5}$$

$$f(m)=0, \text{if } m\equiv 4 \text{ mod 5}$$

And conclude $f(m)\equiv 0 \text{ mod 2}$

So I think you made a mistake with your floor function manipulations.

-