双曲线下方整点个数

hbghlyj

《简明数论》46页 习题六
12. 设 $m, n$ 是正整数, $(m, n)=1$. 证明:
(i) 在以坐标为 $\{0,0\},\{0, m\},\{n, 0\},\{n, m\}$ 为顶点的矩形内部有 $(m-1)(n-1)$ 个整点;
(ii) $\sum_{s=1}^{n-1}\left[\frac{m s}{n}\right]=\frac{1}{2}(m-1)(n-1)$.
13. 设 $m, n$ 是奇正整数, $(m, n)=1$. 证明:
$$
\sum_{0<s<m / 2}\left[\frac{n}{m} s\right]+\sum_{0<t<n / 2}\left[\frac{m}{n} t\right]=\frac{m-1}{2} \cdot \frac{n-1}{2} .
$$
14. 设实数 $C>0$. $M$ 是区域: $x>0, y>0, x y \leqslant C$ 上的整点. 证明:
(i) $M=\sum_{1 \leqslant s \leqslant C}\left[\frac{C}{s}\right]$;
(ii) $M=2 \sum_{1 \leqslant s \leqslant\sqrt{C}}\left[\frac{C}{s}\right]-\left[\sqrt{C}\right]^2$;
(iii) $M=\sum_{1 \leqslant s \leqslant C} \tau(s)$.
(iv) 分别利用(i)(ii)给出计算$M$的近似公式.
────────────────────────────────────────────────────
12. (i) 对于每个$y$, 有$n-1$个整点:$\{1,y\},⋯,\{n-1,y\}$. 对于$y=1,2,⋯,m-1$求和,得出矩形内部共有 $(m-1)(n-1)$ 个整点.
(ii) 由图形关于矩形中心的对称性, 矩形对角线上没有整点, 所以三角形内部的整点个数是矩形内部的整点个数的一半.
13. 在上题中, 当$m,n$为奇数时, 矩形的两条中线$x=\frac n2,y=\frac m2$上没有整点, 所以顶点为 $\left\{0,0\right\},\left\{0,\frac m2\right\},\left\{\frac n2,0\right\},\left\{\frac n2,\frac m2\right\}$的矩形内部的整点个数是全部整点个数的四分之一.
14.(i)对于每个$s$, 有$\{s,1\},\{s,2\},⋯,\{s,\left[\frac{C}{s}\right]\}$共$\left[\frac{C}{s}\right]$个整点.对$s=1,2,⋯,C$求和即可.
(ii) 由图形关于$y=x$的对称性, 注意到$y=x$上有$∑_{1⩽s⩽\sqrt C}\left[\sqrt{C}\right]^2$个整点即可.
(iii) $\tau(s)=∑_{d|s}d$,当$1⩽s⩽C$时,注意到$\left\{d,\frac sd\right\}$是$M$上的整点即可.
(iv) $C / s-1<[C / s]⩽C / s$. 由 (i) 得
$$
C \sum_{1 \leqslant s \leqslant C} 1 / s-[C]<M \leqslant C \sum_{1 \leqslant s \leqslant C} 1 / s .
$$
由 (ii) 得
$$
2 C \sum_{1 \leqslant s \leqslant  \sqrt{C}} 1 / s-C-2 \sqrt{C}<M \leqslant 2 C \sum_{1 \leqslant s \leqslant \sqrt{C}} 1 / s-C+2 \sqrt{C}-1 .
$$

hbghlyj

趣题：2014 年 INMO 中的一个问题
求证，对于任意正整数 $n$，
$$[n/1] + [n/2] + [n/3] + … + [n/n] + [\sqrt n]$$
总是偶数。这里， $[x]$ 表示不超过 $x$ 的最大整数。

容易看出，$[n/1] + [n/2] + [n/3] + … + [n/n]$ 的值，其实就是第一象限里位于函数 $y = \frac nx$ 及其下方的整数格点的个数。 我们把这些点分成两类：位于一三象限角平分线以外的，以及恰好位于一三象限角平分线上的。 前一类的点总是成对地出现，因而一定有偶数个。 但是，后一类点并不是成对出现的。 那么，这些点一共有多少个呢？ 注意到，这些点也就是所有形如 $(i, i)$ 的点，其中 $i^2$ 不能超过 $n$。 因而，这样的点一共有 $[\sqrt n]$ 个。 因此， $[n/1] + [n/2] + [n/3] + … + [n/n] + [\sqrt n]$ 的值，其实就等于这两类点的总个数，其中后一类点被重复计算了两次。 这个值显然应该是偶数。