4
$\begingroup$

Let $5\mid a$, $\gcd(a,b)=1$, and $b\equiv 2\bmod 5$. How can one show that $\sum_{k=1}^{a}k\lfloor\frac{kb}{a}\rfloor\equiv 2\bmod 5$?

Similarly, can we show that if instead $b\equiv 3\bmod 5$, then $\sum_{k=1}^{a}k\lfloor\frac{kb}{a}\rfloor\equiv 3\bmod 5$?

$\endgroup$
1
  • 3
    $\begingroup$ Since $$\sum_{k=1}^{a} k\cdot\frac{kb}{a} = \frac{b}{6}(a+1)(2a+1)\equiv b\pmod{5},$$ we just have to prove that: $$\sum_{k=1}^{a-1}k\cdot\left\{\frac{kb}{a}\right\}\equiv 0\pmod{5}.$$ This seems to be related with the reciprocity law for Dedekind sums. $\endgroup$ Jul 12, 2014 at 6:42

1 Answer 1

5
$\begingroup$

Since $(a,b)=1$, $\left\{\frac{kb}{a}\right\}$ ranges over $\left\{\frac1a,\frac2a,\dots,\frac{a-1}{a}\right\}$. Therefore, $$ \begin{align} \sum_{k=1}^{a-1}\left\{\frac{kb}{a}\right\}^2 &=\sum_{k=1}^{a-1}\left\{\frac{k}{a}\right\}^2\\ &=\frac{(2a-1)(a-1)}{6a}\tag{1} \end{align} $$ However, we also have $\left\{\frac{kb}{a}\right\}=\frac{kb}{a}-\left\lfloor\frac{kb}{a}\right\rfloor$. Therefore, $$ \begin{align} \sum_{k=1}^{a-1}\left\{\frac{kb}{a}\right\}^2 &=\sum_{k=1}^{a-1}\left(\frac{kb}{a}-\left\lfloor\frac{kb}{a}\right\rfloor\right)^2\\ &=\frac{b^2}{a^2}\sum_{k=1}^{a-1}k^2-2\frac{b}{a}\sum_{k=1}^{a-1}k\left\lfloor\frac{kb}{a}\right\rfloor+\sum_{k=1}^{a-1}\left\lfloor\frac{kb}{a}\right\rfloor^2\\ &=\frac{b^2}{a^2}\frac{(2a-1)(a-1)a}{6}-2\frac{b}{a}\sum_{k=1}^{a-1}k\left\lfloor\frac{kb}{a}\right\rfloor+\sum_{k=1}^{a-1}\left\lfloor\frac{kb}{a}\right\rfloor^2\tag{2} \end{align} $$ Subtracting $(2)$ from $(1)$ and multiplying by $a$, we get $$ \begin{align} 2b\sum_{k=1}^{a-1}k\left\lfloor\frac{kb}{a}\right\rfloor =\frac{(b^2-1)(2a-1)(a-1)}{6}+a\sum_{k=1}^{a-1}\left\lfloor\frac{kb}{a}\right\rfloor^2\tag{3} \end{align} $$ If $m\mid a$ and $(m,2b)=1$, then $(3)$ implies $$ \sum_{k=1}^{a-1}k\left\lfloor\frac{kb}{a}\right\rfloor \equiv\frac{b^2-1}{12b}\pmod{m}\tag{4} $$ For $m=5$ and $b\equiv2\pmod{5}$, we get $\frac{b^2-1}{12b}\equiv2\pmod{5}$

For $m=5$ and $b\equiv3\pmod{5}$, we get $\frac{b^2-1}{12b}\equiv3\pmod{5}$


Clarification

Since $(m,2b)=1$, Bezout's Identity says that there are $x,y\in\mathbb{Z}$ so that $$ mx+2by=1\tag{5} $$ Squaring $(5)$ gives $$ m(mx^2+4xby)+4b(by^2)=1\tag{6} $$ Equation $(6)$ implies $$ 4b(by^2)\equiv1\pmod{m}\tag{7} $$ $(7)$ says that $4b$ has an inverse mod $m$.

If $3\not\mid m$, then $(m,3)=1$ and $3$ has an inverse mod $m$.

If $3\mid m$, then $3\not\mid b$. Therefore, $3$ divides either $b-1$ or $b+1$, and thus $3\mid b^2-1$.

Therefore, whether or not $3\mid m$, $(4)$ makes sense.

$\endgroup$
1
  • $\begingroup$ Great solution, as always. $\endgroup$ Jul 15, 2014 at 21:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .