Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
can you edit this to have a proper title using more searchable words, and move the equation into the question? –  Jeff Atwood Apr 23 '11 at 5:23
    
@Jeff: I don't know whether that can be done. I think this is perfect. –  user9413 Apr 23 '11 at 5:43

2 Answers 2

up vote 3 down vote accepted

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{?}$$

share|improve this answer
    
@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. –  Derek Jennings Jan 28 '11 at 22:02
    
sorry Derek. –  anonymous Jan 28 '11 at 22:05
1  
@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. –  Derek Jennings Jan 28 '11 at 22:06

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!)

share|improve this answer
    
$[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. –  anonymous Jan 28 '11 at 2:49
    
You can have a more precise description of when [2x]-2[x] = 0 or 1.. –  Soarer Jan 28 '11 at 3:11
    
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... –  Steven Stadnicki Jan 28 '11 at 3:42

Your Answer

 
discard

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