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$
2
  • 1
    $\begingroup$ You have a double negative there. Do you mean "but $p^2\nmid a$"? $\endgroup$ Commented Jul 13, 2014 at 17:05
  • $\begingroup$ If $a$ and $\hat b$ are coprime, that already implies $p\nmid\hat b$. $\endgroup$ Commented Sep 15, 2014 at 11:39

1 Answer 1

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 and acknowledge you have read our privacy policy.

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