初等数论
----
$1.$ (高联 2009) 证明: 对每对正整数 $k, l$, 有无穷多个 $m$，使得 $(C^k_m, l) = 1.$
令 $m = alk!+k, \ a \in \mathbb{Z_+},$ 则 $ C^k_m = (\frac{ak!}{k}l+1)(\frac{ak!}{k-1}l+1)\cdots(\frac{ak!}{1}l+1)$
因为 $(dl+1,l) = (1, l) = 1, \ d \in \mathbb{Z},$ 可得 $(C^k_m, l) = 1.$
$2.$ (高联 2010) 设 $f^{(0)}(x) = x, \ f^{(1)}(x) = x\lceil x \rceil, \ f^{(l+1)}(x) = f(f^{(l)}(x)),$
证明：如果 $r = k + \frac{1}{2}, \ k \in \mathbb{Z_{\neq 0}},$ 则存在 $m$, 使得 $f^{(m)}(r) \in \mathbb{Z}$.
设 $r = 2^tb + \frac{1}{2}, \ 2 \nmid b,$ 则 $f(r) = (2^tb+\frac{1}{2})(2^tb+1) = 2^{t-1}b(2^{t+1}b + 3) + \frac{1}{2},$
则如果 $r = 2^tb + \frac{1}{2}, \ 2 \nmid b, $ 存在 $m$, 使得 $f^{(m)}(r) \in \mathbb{Z},$
那么 $r = 2^{(t+1)}b + \frac{1}{2}, \ 2 \nmid b, f^{(m+1)}(r) \in \mathbb{Z}.$
又当 $r = (2l + 1) + \frac{1}{2}, l \in \mathbb{Z}$ 时，$f(r) = k(k+1)+(l+1) \in \mathbb{Z},$ 原命题得证.
$3.$ (高联 2012 推广) 给定 $a$ 为大于 $1$ 的正整数, $p$ 为素数, 那么存在正整数 $b$, 使得 $b < pa − 1$ 且
$pa \mid b(b + 1)$ 的充分必要条件是 $a$ 不是 $p$ 的幂.
必要性：若 $a$ 是 $p$ 的幂，即 $a = p^k, \ k \geq 1,$ 命题转变为 $0 < b < p^{k+1}-1,\ p^{k+1} \mid b(b+1).$
由 $(b, b+1) = (b, 1) = 1,$ 得 $p^{k+1} \mid b$ 或 $p^{k+1} \mid b+1,$ 与 $0 < b < p^{k+1}-1$ 显然矛盾.
充分性: 令 $a = p^ks, \ p \nmid s,$ 则 $\exists i \in [1,s-1], \ (p^{k+1}i+1) \mid s,$ 令 $b = p^{k+1}i$ 则满足条件.
$4.$ (高联 2011 T2) 设正整数 $n \geq 4$, 证明: 存在多项式 $f(x)$ 满足条件:
$(1) f(x) = x^n + a_{n-1}x^{n-1} + \cdots a_1x + a_0, \ a_i$ 均为正整数;
$(2)$ 对每个整数 $m$ 以及任意 $k \geq 2$ 个整数 $r_i$, 均有 $f(m) \neq \prod^k_{i=1} f(r_i).$
令 $f(x) = x^{n-2}(x^2+3) + 4(x^{n-1} + x^{n-2} + \cdots + x + 1) + 2,$
则对每个整数 $m$ 以及任意 $k \geq 2$ 个整数 $r_i, \ f(m) \equiv 2 \pmod 4, \ \prod^k_{i=1} f(r_i) \equiv 0 \pmod 4,$ 所以 $f(m) \neq \prod^k_{i=1} f(r_i).$
官方解答： 令 $f(x) = x(x+1)\cdots(x+n-1)+2,$ 其余同理.
$5.$ (高联 2011 T4) 在一个 $3 \times 9$ 的方格中填上一些正整数. 如果有某个矩形中的所有正整数之和为 $10$ 的倍数, 那么称这个矩形为“好矩形”;如果有一个格子不在任何一个“好矩形”中, 则称为“坏格”.求在这个 $3 \times 9$ 的方格中的一种填法, 使得“坏格”最多, 最多为多少?
令 $a_{ij}$ 表示第 $i$ 行第 $j$ 格填上的正整数, $A_{ij} = \sum^j_{k=1} a_{ik}, \ A_i = \sum^{9}_{j=1} A_{ij}.$
下证不存在 $27$ 个坏格：若 $A_{ij} \equiv A_{ik} \pmod {10}(9\geq k>j > 0),$ 则 $A_{ik} - A_{ij} \equiv \sum^k_{h=j+1} a_{ih} \equiv 0 \pmod {10},$ 矛盾.故 $\forall i \in [1,3], \ A_{ij} \bmod 10$ 互不相同且不为 $0$, 即 $A_i \equiv \sum^9_{i=1} i \equiv 5 \pmod {10}.$ 故 $A_1 + A_2 \equiv 0 \pmod {10}.$
又 $A_{1j} + A_{2j}$ 表示矩形 $(1,1)$ 到 $(2,j)$ 的和，同理易得 $A_1 + A_2 \equiv \sum^9_{i=1} i \equiv 5 \pmod {10},$ 矛盾.
下证不存在 $26$ 个坏格：若 $1 \times 1$ 的好矩形在第一行或第三行，由上易得矛盾.若在第二行，咕咕咕...