Let $a$ be a positive proper fraction and $n$ is any integer then evaluate the following sum, $$\sum_{i=1}^{\left \lfloor na \right \rfloor\atop} \left \lfloor ia \right \rfloor $$

I think that probably some counting argument will give us a solution of the problem but I can't find it. Any help is appreciated.

Actually the question aroused due to my efforts in trying to find out a simple formula for calculating the Legendre Symbol. Following is my approach to finding a closed form for the sum $$\sum_{i=1}^{\frac{p-1}{2}} \left \lfloor \dfrac{ia}{p} \right \rfloor $$ where $\operatorname{gcd}(a,p)=1$ and $a$ is odd.

My Try

I have tried to approach the above problem in the following manner. Consider a rectangle in the Cartesian Plane with coordinates of the vertices $A(0,0)$, $B(\dfrac{p}{2},0)$, $C(\dfrac{p}{2},\dfrac{a}{2})$ and $D(0,\dfrac{a}{2})$.

Now draw the two diagonals $AC$ and $BD$. Let them intersect at $O$. Denote the number of lattice points in region $R$ with no lattice point (if any) on the boundaries is counted by $\Lambda(R)$.

Then using this notation we have, $$\Lambda(\triangle AOB)+\Lambda(\triangle BOC)+\Lambda(\triangle COD)+\Lambda(\triangle DOA)=\Lambda(\square ABCD)$$

But since $\triangle AOB \equiv \triangle COD$ and $\triangle BOC \equiv \triangle DOA$, we get $\Lambda(\triangle AOB)=\Lambda(\triangle COD)$ and $\Lambda(\triangle BOC)=\Lambda(\triangle DOA)$

Therefor our expression reduces to, $$2(\Lambda(\triangle AOB)+\Lambda(\triangle BOC)=\Lambda(\square ABCD) \implies 2\Lambda(\triangle ABC)=\Lambda(\square ABCD)$$

But, $$\Lambda(\triangle ABC)=\sum_{i=1}^{\frac{p-1}{2}} \left \lfloor \dfrac{ia}{p} \right \rfloor $$ and $$\Lambda(\square ABCD)=\left(\dfrac{p-1}{2} \right)\left \lfloor \dfrac{a}{2} \right \rfloor$$ hence we have, $$2\sum_{i=1}^{\frac{p-1}{2}} \left \lfloor \dfrac{ia}{p} \right \rfloor=\left(\dfrac{p-1}{2} \right)\left(\dfrac{a-1}{2} \right )$$

But from this I can't interpret the given sum. What is the mistake? There must be a mistake because the parity of both side of the inequality doesn't hold if $p \equiv a \equiv 3$ $(\operatorname{mod}4)$. Can anyone help me in this respect?


2 Answers 2


Let $a = \displaystyle\frac{p}{q}$ where $(p,q) = 1$ and $p < q$. Then:

$$\sum_{i=1}^{\lfloor na\rfloor} \lfloor ia \rfloor = \sum_{i=1}^{\lfloor na\rfloor} ia - \sum_{i=1}^{\lfloor na\rfloor} \lbrace ia \rbrace $$

Where $\lbrace x\rbrace$ is the fractional part of $x$.

Note that:

$$\sum_{i=1}^{\lfloor na\rfloor} \lbrace ia \rbrace = \frac{1}{q}\sum_{i=1}^{\lfloor na\rfloor} ip\text{ mod }q $$

We can get some interesting results from that depending on $n \text{ mod }q$.

  • $\begingroup$ Could you elaborate on how you got to the second summation involving mod q. $\endgroup$
    – KBusc
    Aug 19, 2014 at 20:00
  • $\begingroup$ @KBusc Using integer division we have $ip = cq + r$ where $0 \leq r < q$ (in fact, $r = ip \mod q$ and $c = \lfloor ia\rfloor$) so $\frac{ip}{q} = c + \frac{r}{q} = \lfloor ai\rfloor + \frac{ip\mod q}{q}$ $\endgroup$
    – Darth Geek
    Aug 19, 2014 at 20:23
  • $\begingroup$ Ahh thank you very much, that makes sense. $\endgroup$
    – KBusc
    Aug 20, 2014 at 12:10
  • $\begingroup$ Can't there be obtained any closed form of the sum? $\endgroup$
    – user170039
    Aug 20, 2014 at 12:37
  • $\begingroup$ @user170039 that depends on the divisibility of $n$ by $q$ and on wether $q$ is prime or not. $\endgroup$
    – Darth Geek
    Aug 20, 2014 at 12:39

Not quite an answer but I couln't get this to look correct as comment. But I think $$ 0 <\sum_{i=1}^{\left \lfloor na \right \rfloor} \left \lfloor ia \right \rfloor < a\cdot {\left \lfloor na \right \rfloor}\frac{{\left \lfloor na \right \rfloor} + 1}{2} $$

Should be true.

  • $\begingroup$ Sorry for the terrible syntax but I am not sure how to do the fraction correctly $\endgroup$
    – KBusc
    Aug 19, 2014 at 18:02
  • $\begingroup$ Try \frac{ numerator } { denominator } or just { numerator \over denominator } $\endgroup$
    – Winther
    Aug 19, 2014 at 18:02
  • 1
    $\begingroup$ You are missing a factor of $a$. Since $\lfloor ia \rfloor \leq ia$ we have $\sum \lfloor ia \rfloor \leq a \cdot \frac{\lfloor na \rfloor(\lfloor na \rfloor + 1)}{2}$. $\endgroup$
    – Winther
    Aug 19, 2014 at 18:06

You must log in to answer this question.