MHB What is the Proof for the Floor Function Challenge II Involving Primes?

[anemone]

Let $a$ and $b$ be two different primes. Prove that
$\displaystyle\left\lfloor\dfrac{a}{b} \right\rfloor+\left\lfloor\dfrac{2a}{b} \right\rfloor+\left\lfloor\dfrac{3a}{b} \right\rfloor+\cdots+\left\lfloor\dfrac{(b-1)a}{b} \right\rfloor=\dfrac{(a-1)(b-1)}{2}$.

 

[Euge]

Spoiler

For every $k \in \{1,2,\ldots,b-1\}$, $ka$ is not divisible by $b$ (or else $b$ divides $k$, which cannot happen). So for fixed $k$,

$\displaystyle \frac{ka}{b} - 1 < \left\lfloor\frac{ka}{b}\right\rfloor < \frac{ka}{b}$,

$\displaystyle \frac{(b-k)a}{b} - 1 < \left\lfloor\frac{(b-k)a}{b}\right\rfloor < \frac{(b-k)a}{b}$.

Adding the two inequalities, we get

$\displaystyle a - 2 < \left\lfloor\frac{ka}{b}\right\rfloor + \left\lfloor\frac{(b-k)a}{b}\right\rfloor < a$.

This forces

$\displaystyle \left\lfloor\frac{ka}{b}\right\rfloor + \left\lfloor\frac{(b-k)a}{b}\right\rfloor = a - 1$

Therefore

$\displaystyle \left\lfloor\frac{a}{b}\right\rfloor + \left\lfloor\frac{2a}{b}\right\rfloor + \cdots + \left\lfloor\frac{(b-1)a}{b}\right\rfloor$

$\displaystyle = \dfrac{\left\lfloor\frac{a}{b}\right\rfloor + \left\lfloor\frac{(b-1)a}{b}\right\rfloor}{2} + \dfrac{\left\lfloor\frac{2a}{b}\right\rfloor + \left\lfloor\frac{(b-2)a}{b}\right\rfloor}{2} + \cdots + \dfrac{\left\lfloor\frac{(b-1)a}{b}\right\rfloor + \left\lfloor\frac{a}{b}\right\rfloor}{2}$

$\displaystyle = \frac{a-1}{2} + \frac{a-1}{2} + \cdots + \frac{a-1}{2} (b-1\; \text{times})$

$\displaystyle = \frac{(a-1)(b-1)}{2}$.

 

[anemone]

Spoiler

For every $k \in \{1,2,\ldots,b-1\}$, $ka$ is not divisible by $b$ (or else $b$ divides $k$, which cannot happen). So for fixed $k$,

$\displaystyle \frac{ka}{b} - 1 < \left\lfloor\frac{ka}{b}\right\rfloor < \frac{ka}{b}$,

$\displaystyle \frac{(b-k)a}{b} - 1 < \left\lfloor\frac{(b-k)a}{b}\right\rfloor < \frac{(b-k)a}{b}$.

Adding the two inequalities, we get

$\displaystyle a - 2 < \left\lfloor\frac{ka}{b}\right\rfloor + \left\lfloor\frac{(b-k)a}{b}\right\rfloor < a$.

This forces

$\displaystyle \left\lfloor\frac{ka}{b}\right\rfloor + \left\lfloor\frac{(b-k)a}{b}\right\rfloor = a - 1$

Therefore

$\displaystyle \left\lfloor\frac{a}{b}\right\rfloor + \left\lfloor\frac{2a}{b}\right\rfloor + \cdots + \left\lfloor\frac{(b-1)a}{b}\right\rfloor$

$\displaystyle = \dfrac{\left\lfloor\frac{a}{b}\right\rfloor + \left\lfloor\frac{(b-1)a}{b}\right\rfloor}{2} + \dfrac{\left\lfloor\frac{2a}{b}\right\rfloor + \left\lfloor\frac{(b-2)a}{b}\right\rfloor}{2} + \cdots + \dfrac{\left\lfloor\frac{(b-1)a}{b}\right\rfloor + \left\lfloor\frac{a}{b}\right\rfloor}{2}$

$\displaystyle = \frac{a-1}{2} + \frac{a-1}{2} + \cdots + \frac{a-1}{2} (b-1\; \text{times})$

$\displaystyle = \frac{(a-1)(b-1)}{2}$.

Wow...what terrific solution, so impressively laid out...well done, Euge! And thanks for participating.:)

I have at hand a solution that tackles the problem entirely differently and I would post it days later, in case there are more members want to play with this problem.

 

[anemone]

Solution of other:

Spoiler

The statement involves two independent variables, $a$ and $b$ and $\dfrac{a}{b},\,\dfrac{2a}{b},\,\dfrac{3a}{b},\cdots,$ respectively. We might want to approach it using geometry approach.

Consider the case $a=5$ and $b=7$. The points $(k,\,\dfrac{5k}{7})$ where $k=1,\,2,\,\cdots,\,6$ each lie on the line $y=\dfrac{5k}{7}$ and $\displaystyle \sum_{k=1}^6\left\lfloor\dfrac{5k}{7} \right\rfloor$ equals the number of lattice points interior to the triangle with vertices $(0,\,0)$, $(7,\,0)$ and $(7,\,5)$. By symmetry, this number is one-half the number of lattice points in the rectangle with vertices $(0,\,0)$, $(0,\,5)$, $(7,\,0)$ and $(7,\,5)$. There are $4\times 6=24$ lattice points in that rectangle, which means the triangle with vertices $(0,\,0)$, $(7,\,0)$ and $(7,\,5)$ contains 12 interior lattice points.

The same goes through in the general case. The condition that $a$ and $b$ have no common factor assures us that none of the lattice points in the interior of the rectangle will fall on the line $y=\dfrac{ax}{b}$. Thus,

$\displaystyle \sum_{k=1}^{b-1}\left\lfloor\dfrac{ka}{b} \right\rfloor=\dfrac{\text{total number of lattice poins in the interior of the rectangle}}{2}=\frac{(a-1)(b-1)}{2}$.

 

[mathbalarka]

Interestingly done anemone. Reminds me of a post I made long ago in http://mathhelpboards.com/number-theory-27/quadratic-reciprocity-9722.html at the number theory forum.