设 $p,q$ 互素, 证明
\[
\sum_{k=0}^{pq-1}(-1)^{[\frac{k}{p}]+[\frac{k}{q}]}=
\begin{cases}
0, & pq\ \text{是偶数},\\
1, & pq\ \text{是奇数}.\\
\end{cases}
\]
这里 [ ] 是指取整.
(Proposed by Alexander Bolbot, State University, Novosibirsk)
[Hint] 当 $pq$ 为偶数时, 由于 $p,q$ 互素, 故它们的奇偶性不同. 令 $a_k=(-1)^{[\frac{k}{p}]+[\frac{k}{q}]}$, 证明
\[
a_k+a_{pq-1-k}=0.
\]
1
(1) 首先假设 $pq$ 是偶数, 由于 $(p,q)=1$, 故 $p$ 和 $q$ 的奇偶性不同.
令 $a_k=(-1)^{[\frac{k}{p}]+[\frac{k}{q}]}$, 我们证明
\[
a_k+a_{pq-1-k}=0.
\]
从而所要证明的等式左边两两相消, 结果为 0.
注意到, 对每个正整数 $k$, 我们有
\[
\Bigl\{\frac{k}{p}\Bigr\}+\Bigl\{\frac{p-1-k}{p}\Bigr\}=\frac{p-1}{p}.
\]
因此
\[
\Bigl\lfloor\frac{k}{p}\Bigr\rfloor+\Bigl\lfloor\frac{pq-1-k}{p}\Bigr\rfloor=\Bigl(\frac{k}{p}-\Bigl\{\frac{k}{p}\Bigr\}\Bigr)+\Bigl(\frac{pq-1-k}{p}-\Bigl\{\frac{-1-k}{p}\Bigr\}\Bigr)=\frac{pq-1}{p}-\frac{p-1}{p}=q-1.
\]
类似地,
\[
\Bigl\lfloor\frac{k}{q}\Bigr\rfloor+\Bigl\lfloor\frac{pq-1-k}{q}\Bigr\rfloor=p-1.
\]
由于 $p,q$ 的奇偶性不同, 这推出 $\bigl\lfloor\frac{k}{p}\bigr\rfloor+\bigl\lfloor\frac{k}{q}\bigr\rfloor$ 和 $\bigl\lfloor\frac{pq-1-k}{p}\bigr\rfloor+\bigl\lfloor\frac{pq-1-k}{q}\bigr\rfloor$ 也具有不同的奇偶性. 因此 $a_{pq-1-k}=-a_{k}$.
(2) 假设 $pq$ 是奇数. 对任意 $k$, 记 $p_k$, $q_k$ 分别为 $k$ 关于模 $p$ 和模 $q$ 的剩余. (即有 $0\leqslant p_k < p$, $0\leqslant q_k < q$, 使得 $k\equiv p_k\pmod p$, $k\equiv q_k\pmod q$.)
注意到
\[
\Bigl\lfloor\frac{k}{p}\Bigr\rfloor+\Bigl\lfloor\frac{k}{q}\Bigr\rfloor\equiv p\Bigl\lfloor\frac{k}{p}\Bigr\rfloor+q\Bigl\lfloor\frac{k}{q}\Bigr\rfloor=(k-p_k)+(k-q_k)\equiv p_k+q_k\pmod 2 .
\]
由于 $p,q$ 是互素的, 根据中国剩余定理, 映射 $k\mapsto(p_k,q_k)$ 是集合 $\{0,1,2,\ldots,pq-1\}$ 到集合 $\{0,1,2,\ldots,p-1\}\times\{0,1,2,\ldots,q-1\}$ 的一个双射. 因此,
\[
\sum_{k=0}^{pq-1}(-1)^{\lfloor\frac{k}{p}\rfloor+\lfloor\frac{k}{q}\rfloor}=\sum_{k=0}^{pq-1}(-1)^{p_k+q_k}=\sum_{i=0}^{p-1}\sum_{j=0}^{q-1}(-1)^{i+j}=\biggl(\sum_{i=0}^{p-1}(-1)^i\biggr)\cdot\biggl(\sum_{j=0}^{q-1}(-1)^j\biggr)=1.
\]