# Fractional Part Problem

Suppose we have coprime integers $a$ and $b$ with $p \mid a$ but $p^2 \nmid a$ for some prime $p\geq 5$. We can write $a=px$ and $b=pr+\hat{b}$. Suppose also that $a$ and $\hat{b}$ are coprime; that is to say, $\hat{b}$ and $x$ are coprime. Consider the set:

$$S=\left\{k<a\mid\{\tfrac{kr}{x}\}+\{\tfrac{k\hat{b}}{a}\}\geq 1\right\}$$

Using elementary results from fractional part theory, one can prove:

$$|S|=\frac{p(x-\gcd(r,x))}{2}$$

Define the following $p$ subsets of $S$, $S_0$ through $S_{p-1}$:

$$S_i=\left\{k<a\text{ and }k\equiv i\pmod p\mid\{\tfrac{kr}{x}\}+\{\tfrac{k\hat{b}}{a}\}\geq 1\right\}$$

These sets divide the terms in $S$ into their residue classes. We claim that for any $i$,

$$|S_i|=\frac{x-\gcd(r,x)}{2}$$

Can we prove this?

• You have a double negative there. Do you mean "but $p^2\nmid a$"? – Robert Israel Jul 13 '14 at 17:05
• If $a$ and $\hat b$ are coprime, that already implies $p\nmid\hat b$. – Emil Jeřábek Sep 15 '14 at 11:39

It seems that the counting of elements in $S_i$ can be made in the same way as the counting of those in $S$.
For simplicity, I rename $y=r$, $z=\hat b$.
Let $T=\{k<a\}\setminus S$. Then it is easy to see that $$S=\left\{k<a\colon \left\{k\cdot \frac{py}{px}\right\}+\left\{k\cdot \frac{z}{pr}\right\} =1+\left\{k\cdot \frac{py+z}{px}\right\}\right\}$$ and $$T=\left\{k<a\colon \left\{k\cdot \frac{py}{px}\right\}+\left\{k\cdot \frac{z}{pr}\right\} =\left\{k\cdot \frac{py+z}{px}\right\}\right\}.$$ Thus, $$|S|=\sum_{k<a}\left\{k\cdot \frac{py}{px}\right\} +\sum_{k<a}\left\{k\cdot \frac{z}{px}\right\} -\sum_{k<a}\left\{k\cdot \frac{py+z}{px}\right\}.$$
Similarly, $$|S_i|=\Sigma_i(py)+\Sigma_i(z)-\Sigma_i(py+z), \qquad \text{where}\quad \Sigma_i(d)=\sum_{k<a,k\equiv i\pmod p}\left\{k\cdot \frac{d}{px}\right\}. \qquad(*)$$
Now let $d$ be any integer. Set $\mu=\gcd(d,x)$, $d'=d/\mu$, $x'=x/\mu$ and choose $j<p$ with $id'\equiv j\pmod p$. When $k$ runs over the numbers congruent to $i$ modulo $p$, the residue of $kd'=id'+(k-i)d'$ modulo $px'$ runs over all the numbers of the form $j+p\ell$ with $\ell<x'$. Then we have \begin{align*} \Sigma_i(d)&=\sum_{k<a,k\equiv i\pmod p}\left\{\frac{kd'}{px'}\right\} =\mu\sum_{\ell=0}^{x'-1}\frac{j+p\ell}{px'} =\frac{\mu j}p+\mu\cdot\frac{x'-1}2=\frac{\mu j}p+\frac{x-\mu}2. \qquad (**) \end{align*}
Return to $(*)$. Using $\gcd(py+z,x)=\gcd(z,x)=1$ and $iz\equiv i(py+z)\pmod p$, from $(**)$ we get $\Sigma_i(py+z)=\Sigma_i(z)$. Thus from $(*)$ and $(**)$ we obtain \begin{align*} |S_i|=\Sigma_i(py) =\frac{x-\gcd(py,x)}2, \end{align*} as required.