I was working out some problems. This is giving me trouble.

  • If $p$ is a prime number of the form $4n+1$ then how do i show that:

$$ \sum\limits_{i=1}^{p-1} \Biggl( \biggl\lfloor{\frac{2i^{2}}{p}\biggr\rfloor}-2\biggl\lfloor{\frac{i^{2}}{p}\biggr\rfloor}\Biggr)= \frac{p-1}{2}$$

Two things which i know are:

  • If $p$ is a prime of the form $4n+1$, then $x^{2} \equiv -1 \ (\text{mod} \ p)$ can be solved.

  • $\lfloor{2x\rfloor}-2\lfloor{x\rfloor}$ is either $0$ or $1$.

I think the second one will be of use, but i really can't see how i can apply it here.

  • $\begingroup$ can you edit this to have a proper title using more searchable words, and move the equation into the question? $\endgroup$ – Jeff Atwood Apr 23 '11 at 5:23
  • $\begingroup$ @Jeff: I don't know whether that can be done. I think this is perfect. $\endgroup$ – user9413 Apr 23 '11 at 5:43
  • $\begingroup$ It is fine the way it is I can assure you Jeff was probably having a drug induced psychosis again $\endgroup$ – Adam Sep 28 '18 at 22:24

Here are some more detailed hints.

Consider the value of $\lfloor 2x \rfloor - 2 \lfloor x \rfloor$ where $x=n+ \delta$ for $ n \in \mathbb{Z}$ and $0 \le \delta < 1/2.$

Suppose $p$ is a prime number of the form $4n+1$ and $a$ is a quadratic residue modulo $p$ then why is $(p-a)$ also a quadratic residue?

What does this say about the number of quadratic residues $< p/2$ ?

All the quadratic residues are congruent to the numbers $$1^2,2^2,\ldots, \left( \frac{p-1}{2} \right)^2,$$ which are themselves all incongruent to each other, so how many times does the set $\lbrace 1^2,2^2,\ldots,(p-1)^2 \rbrace$ run through a complete set of $\it{quadratic}$ residues?

Suppose $i^2 \equiv a \textrm{ mod } p$ where $i \in \lbrace 1,2,\ldots,p-1 \rbrace$ and $a$ is a quadratic residue $< p/2$ then what is the value of

$$ \left \lfloor \frac{2i^2}{p} \right \rfloor - 2 \left \lfloor \frac{i^2}{p} \right \rfloor \quad \text{?}$$

  • $\begingroup$ @Chandru1 Please don't change maths in my answer, although I'm very happy for you to correct typos. Please put your ideas in the comments instead. Many thanks. $\endgroup$ – Derek Jennings Jan 28 '11 at 22:02
  • $\begingroup$ sorry Derek. $\endgroup$ – anonymous Jan 28 '11 at 22:05
  • 1
    $\begingroup$ @Chandru1: We know $x^2 \equiv a$ and since $p=4n+1$ we have $y^2 \equiv -1$ and so $(xy)^2 \equiv -a \equiv p-a.$ I hope this helps. $\endgroup$ – Derek Jennings Jan 28 '11 at 22:06
  • $\begingroup$ wow incredible response infinitely impressed Sir $\endgroup$ – Adam Sep 28 '18 at 22:50

Without giving everything away: when is $\lfloor2x\rfloor - 2\lfloor x\rfloor$ equal to $0$, and when is it equal to $1$? Can you find some bijection between values of $i$ in your sum that fall into the first camp, and those that fall into the second? (You may find the other fact you gave to be useful for finding this bijection!)

  • $\begingroup$ $[2x]-2[x]$ is $0$ when $x \in \mathbb{Z}$, so using this i think it will be $0$ when $p \mid i^{2}$ or something like that. $\endgroup$ – anonymous Jan 28 '11 at 2:49
  • $\begingroup$ You can have a more precise description of when [2x]-2[x] = 0 or 1.. $\endgroup$ – Soarer Jan 28 '11 at 3:11
  • $\begingroup$ What Soarer said - what can you say about [2x]-2[x] w.r.t. x mod 1? If this isn't enough hint, incidentally (and assuming this isn't homework, of course!), I can give you the full answer tomorrow, but I think it's worth trying to puzzle through on your own... $\endgroup$ – Steven Stadnicki Jan 28 '11 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy