2
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.