Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.