Let $\alpha\ge 1$ be an even integer, and $k$ an intger s.t, $1\le k\le \alpha$. Set $\alpha'=\alpha/2$, $$ A=\mathrm{Card}(\{n : 0\le n\le k-1, k\mid\alpha'(4n+1)\}),\quad B=\mathrm{Card}(\{n : 0\le n\le k-1, k\mid\alpha'(4n+3)\}) $$ So my question is: Can we find $A$ and $B$ explicitly in terms of $\alpha'$ and $k$? I tried with some examples and I suspect that, if $2^g\mid\mid \alpha$ (i.e., $\alpha=2^g\beta$ with $\gcd(\beta,2)=1$) then

$$ A=B=\left\{ \begin{array}{cc} 0 & \mbox{if} \;k\; \mbox{multiple of} \;2^g\\ \gcd(\alpha',k) & \mbox{otherwise.} \\ \end{array} \right. $$ I am pretty sure that this is true,but I don't know how to prove it formally.


This is a straightforward exercise in elementary number theory, but I felt like doing it.

For any integer $m$, the relation $k\mid\alpha'm$ is equivalent to $\frac{k}{\gcd(k,\alpha')}\mid m$. $A$ is the number of such $m$'s with the additional properties $m\equiv 1\pmod{4}$ and $1\leq m<4k+1$, while $B$ is the number of such $m$'s with the additional properties $m\equiv 3\pmod{4}$ and $3\leq m<4k+3$. As both $A$ and $B$ count odd integers, they are zero unless $\frac{k}{\gcd(k,\alpha')}$ is odd, i.e. the exponent of $2$ in $k$ is at most the exponent of $2$ in $\alpha'$, i.e. $2^g\nmid k$. Now assume that this is the case, then by the Chinese remainder theorem both $A$ and $B$ count integers $m$ that lie in a fixed residue class modulo $\frac{4k}{\gcd(k,\alpha')}$ and also in an interval of $4k$ consecutive integers. Hence both $A$ and $B$ equal $4k$ divided by $\frac{4k}{\gcd(k,\alpha')}$, which is $\gcd(k,\alpha')$.

  • $\begingroup$ @user0154468764: You are welcome! $\endgroup$ – GH from MO Feb 2 '18 at 13:28

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.