设 $\tau (n)$ 为 $n$ 的正因数的个数,$\tau_1 (n)$ 为 $n$ 模 $3$ 余 $1$ 的正因数的个数.求 $\frac{\tau(10n)}{\tau_1 (10n)}$ 所有整数值.
【难度】
【出处】
2016IMO Short List
【标注】
【答案】
$2$ 与全部合数.
用 $p_i$ 表示模 $3$ 余 $1$ 的素数,用 $q_j$ 表示模 $3$ 余 $2$ 的素数.当用素因子表示 $m$ 时,也包含特殊情况 $m=1$(允许幂为 $0$).
先证明一个引理.
引理:
设 $m=3^x p_1^{a_1} p_2^{a_2} \ldots p_s^{a_s} q_1^{b_1} q_2^{b_2}\ldots q_t^{b_t}$ 为 $m$ 的素因数分解式.则\begin{equation}
\tau_{1}(m)=\left(\prod_{i=1}^{s}\left(a_{i}+1\right)\right)\lceil\frac{1}{2} \prod_{j=1}^{t}\left(b_{j}+1\right)\rceil
\end{equation}引理的证明:为了选择 $m$ 的模 $3$ 余 $1$ 的正因数,其不能有素因数 $3$,而模 $3$ 余 $1$ 的素因数不受限制,且必须选取偶数个模 $3$ 余 $2$ 的素因数(按重数计算).若 $\prod_{j=1}^{t}(b_j +1)$ 为偶数,不失一般性,不妨假设 $b_1 +1$ 为偶数.则有 $\prod_{j=2}^{t}(b_j+1)$ 种方法任意地选择素因数 $q_2 ,q_3 ,\ldots,q_t$.于是,$q_1$ 的个数的奇偶性唯一确定.从而,有 $\frac{1}{2}(b_1 +1)$ 种方法选择 $q_1$.因此,式(1)成立.
若 $\prod_{j=1}^{t}(b_j +1)$ 为奇数,对 $t$ 用数学归纳法来计算选择的方法种数.当 $t=1$ 时,则有 $\lceil\frac{b_1 +1}{2}\rceil$ 种方法选择幂为偶数.有 $\lfloor\frac{b_1 +1}{2}\rfloor$ 种方法选择幂为奇数.于是,结论成立.
假设对 $t-1$ 时结论成立.由归纳假设有$$\lceil \frac{1}{2}\prod_{j=1}^{t-1}(b_j +1)\rceil \lceil \frac{b_t +1}{2}\rceil + \lfloor \frac{1}{2}\prod_{j=1}^{t} (b_j +1)\rfloor \lfloor \frac{b_t +1}{2}\rfloor = \lceil \frac{1}{2}\prod_{j=1}^{t} (b_j +1)\rceil$$种方法选择偶数个素因数.故有 $\lfloor\frac{1}{2}\prod_{j=1}^{t}(b_j +1)\rfloor$ 种方法选择奇数个素因数.因此,式(1)也成立.引理得证.
设 $n=3^x \times 2^y \times 5^z p_1^{a_1} p_2^{a_2}\ldots p_s^{a_s} q_1^{b_1} q_2^{b_2}\ldots q_t^{a_t}$.则\begin{equation}
\tau(10 n)=(x+1)(y+2)(z+2)\left(\prod_{i=1}^{s}(a_i +1)\right)\left(\prod_{j=1}^{t}(b_j +1)\right)
\end{equation}由引理得\begin{equation}
\tau_1 (10 n)=\left(\prod_{i=1}^{s}(a_i +1)\right)\lceil\frac{1}{2}(y+2)(z+2)\prod_{j=1}^{t}(b_j +1)\rceil
\end{equation}若 $c=(y+2)(z+2)\prod_{j=1}^{t}(b_j +1)$ 为偶数,则由式(2),(3)得$$\frac{\tau(10n)}{\tau_1 (10n)}=2(x+1)$$当 $x$ 取遍所有非负整数时,$\frac{\tau(10n)}{\tau_1 (10n)}$ 取遍所有的偶数.
若 $c$ 为奇数,这表明,$y,z$ 也为奇数,每个 $b_j$($j=1,2,\ldots,t$)均为偶数.由式(2),(3)得\begin{equation}
\frac{\tau(10n)}{\tau_1 (10n)}=\frac{2(x+1)c}{c+1}
\end{equation}为使 $\frac{\tau(10n)}{\tau_1 (10n)}$ 为整数,由于 $(c,c+1)=1$,故 $(c+1)~|~2(x+1)$.设 $2(x+1)=k(c+1)$.则\begin{equation}
\frac{\tau(10n)}{\tau_1 (10n)}=kc=k(y+2)(z+2)\prod_{j=1}^{t}(b_j +1)
\end{equation}由于 $y,z$ 为奇数,于是,$y+2,z+2$ 至少为 $3$.这表明,整数 $\frac{\tau(10n)}{\tau_1 (10n)}$ 必为合数.又对于任意奇合数 $ab$($a,b\geqslant 3$),取$$n=3^{\frac{ab-1}{2}}\times 2^{a-2}\times 5^{b-2}$$由式(5)知 $\frac{\tau(10n)}{\tau_1 (10n)}=ab$.
综上,$\frac{\tau(10n)}{\tau_1 (10n)}$ 可以为任意偶数及任意奇合数,这等价于 $2$ 与全部合数
用 $p_i$ 表示模 $3$ 余 $1$ 的素数,用 $q_j$ 表示模 $3$ 余 $2$ 的素数.当用素因子表示 $m$ 时,也包含特殊情况 $m=1$(允许幂为 $0$).
先证明一个引理.
引理:
设 $m=3^x p_1^{a_1} p_2^{a_2} \ldots p_s^{a_s} q_1^{b_1} q_2^{b_2}\ldots q_t^{b_t}$ 为 $m$ 的素因数分解式.则\begin{equation}
\tau_{1}(m)=\left(\prod_{i=1}^{s}\left(a_{i}+1\right)\right)\lceil\frac{1}{2} \prod_{j=1}^{t}\left(b_{j}+1\right)\rceil
\end{equation}引理的证明:为了选择 $m$ 的模 $3$ 余 $1$ 的正因数,其不能有素因数 $3$,而模 $3$ 余 $1$ 的素因数不受限制,且必须选取偶数个模 $3$ 余 $2$ 的素因数(按重数计算).若 $\prod_{j=1}^{t}(b_j +1)$ 为偶数,不失一般性,不妨假设 $b_1 +1$ 为偶数.则有 $\prod_{j=2}^{t}(b_j+1)$ 种方法任意地选择素因数 $q_2 ,q_3 ,\ldots,q_t$.于是,$q_1$ 的个数的奇偶性唯一确定.从而,有 $\frac{1}{2}(b_1 +1)$ 种方法选择 $q_1$.因此,式(1)成立.
若 $\prod_{j=1}^{t}(b_j +1)$ 为奇数,对 $t$ 用数学归纳法来计算选择的方法种数.当 $t=1$ 时,则有 $\lceil\frac{b_1 +1}{2}\rceil$ 种方法选择幂为偶数.有 $\lfloor\frac{b_1 +1}{2}\rfloor$ 种方法选择幂为奇数.于是,结论成立.
假设对 $t-1$ 时结论成立.由归纳假设有$$\lceil \frac{1}{2}\prod_{j=1}^{t-1}(b_j +1)\rceil \lceil \frac{b_t +1}{2}\rceil + \lfloor \frac{1}{2}\prod_{j=1}^{t} (b_j +1)\rfloor \lfloor \frac{b_t +1}{2}\rfloor = \lceil \frac{1}{2}\prod_{j=1}^{t} (b_j +1)\rceil$$种方法选择偶数个素因数.故有 $\lfloor\frac{1}{2}\prod_{j=1}^{t}(b_j +1)\rfloor$ 种方法选择奇数个素因数.因此,式(1)也成立.引理得证.
设 $n=3^x \times 2^y \times 5^z p_1^{a_1} p_2^{a_2}\ldots p_s^{a_s} q_1^{b_1} q_2^{b_2}\ldots q_t^{a_t}$.则\begin{equation}
\tau(10 n)=(x+1)(y+2)(z+2)\left(\prod_{i=1}^{s}(a_i +1)\right)\left(\prod_{j=1}^{t}(b_j +1)\right)
\end{equation}由引理得\begin{equation}
\tau_1 (10 n)=\left(\prod_{i=1}^{s}(a_i +1)\right)\lceil\frac{1}{2}(y+2)(z+2)\prod_{j=1}^{t}(b_j +1)\rceil
\end{equation}若 $c=(y+2)(z+2)\prod_{j=1}^{t}(b_j +1)$ 为偶数,则由式(2),(3)得$$\frac{\tau(10n)}{\tau_1 (10n)}=2(x+1)$$当 $x$ 取遍所有非负整数时,$\frac{\tau(10n)}{\tau_1 (10n)}$ 取遍所有的偶数.
若 $c$ 为奇数,这表明,$y,z$ 也为奇数,每个 $b_j$($j=1,2,\ldots,t$)均为偶数.由式(2),(3)得\begin{equation}
\frac{\tau(10n)}{\tau_1 (10n)}=\frac{2(x+1)c}{c+1}
\end{equation}为使 $\frac{\tau(10n)}{\tau_1 (10n)}$ 为整数,由于 $(c,c+1)=1$,故 $(c+1)~|~2(x+1)$.设 $2(x+1)=k(c+1)$.则\begin{equation}
\frac{\tau(10n)}{\tau_1 (10n)}=kc=k(y+2)(z+2)\prod_{j=1}^{t}(b_j +1)
\end{equation}由于 $y,z$ 为奇数,于是,$y+2,z+2$ 至少为 $3$.这表明,整数 $\frac{\tau(10n)}{\tau_1 (10n)}$ 必为合数.又对于任意奇合数 $ab$($a,b\geqslant 3$),取$$n=3^{\frac{ab-1}{2}}\times 2^{a-2}\times 5^{b-2}$$由式(5)知 $\frac{\tau(10n)}{\tau_1 (10n)}=ab$.
综上,$\frac{\tau(10n)}{\tau_1 (10n)}$ 可以为任意偶数及任意奇合数,这等价于 $2$ 与全部合数
【解析】
略
答案
解析
备注