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!

  • 5
    $\begingroup$ Are you only interested in answers that do it your way, or would you also be interested in answers that use quadratic reciprocity? $\endgroup$ – Zev Chonoles Jul 28 '13 at 15:16
  • $\begingroup$ math.stackexchange.com/questions/236083/… $\endgroup$ – lab bhattacharjee Jul 28 '13 at 15:16
  • $\begingroup$ @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. $\endgroup$ – 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.


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.