A question of divisibility.

Question

Let $p$ and $q$ are relatively prime integers.

Consider $S = \{\frac{p}{q}\} + \{\frac{2p}{q}\} + \{\frac{(q-1)p}{q}\}$, where $\{x\}$ is the fractional part of the real number $x$.

Prove that $2S$ is divisible by $(q-1)$.

I could not do much with it. May be a very easy problem but I could not do it. $S$ is a fraction, may not a natural number. But $2S$ is an integer and divisible by $(q-1)$, an integer. How ?

Answer 1

Let $S = \sum_{i=1}^{q-1} \{ \frac{ip}{q} \}$. Since $p$ and $q$ are relatively prime, multiplication by $p$ permutes the nonzero residues mod $q$, and so $$ S = \sum_{i=1}^{q-1} \{ \frac{ip}{q} \} = \sum_{i=1}^{q-1} \{ \frac{i}{q} \} = \frac 1q \sum_{i=1}^{q-1} i = \frac 1q \cdot \frac{q(q-1)}{2} = \frac{q-1}{2} . $$

Answer 2

HINT: $S = \{\frac{p}{q}\} + \{\frac{2p}{q}\} + \{\frac{(q-1)p}{q}\} = \sum\limits_{j=1}^{q-1} (\frac{jp}{q}-[\frac{jp}{q}])$

$2S=\sum\limits_{j=1}^{q-1} (\frac{jp}{q}+\frac{(q-j)p}{q})+2\sum\limits_{j=1}^{q-1} ([\frac{jp}{q}])=p(q-1)-2N$, where $N$ is the number of lattice points under the line $y=\frac{p}{q}x$ between $x=1$ to $x=q-1$. Since, $gcd(p,q)=1$, the number of lattice points on the line $y=\frac{p}{q}x$ between $x=1$ to $x=q-1$ is $0$ (why ??).

So, $2N=\sum\limits_{j=1}^{q-1} ([\frac{jp}{q}]+[\frac{(q-j)p}{q}])$ gives the number of lattice points in the box $x=1$ to $x=q-1$ and $y=1$ to $y=p-1$; that is $(p-1)(q-1)$.

Therefore, $2S=p(q-1)-(p-1)(q-1)=q-1$.