求一个数 $k$，使得对所有 $n$，$k\cdot 2^n+1$ 都是合数．
【难度】
【出处】
2016年华东师范大学新生入学考试题
【标注】
【答案】
略
【解析】
我们尝试构造一个满足条件的 $k$．
情形一 当 $n=2m$ 时，有\[k\cdot 2^n+1\equiv k+1\pmod 3,\]于是当 $k\equiv -1\pmod 3$ 时，有 $3\mid k\cdot 2^n+1$．
情形二 当 $n=3m$ 时，有\[k\cdot 2^n+1\equiv k+1\pmod 7,\]于是当 $k\equiv -1\pmod 7$ 时，有 $7\mid k\cdot 2^n+1$．
情形三 当 $n=6m+1$ 时，由于 $2^6+1=13\cdot 5$，于是
（i）$m=2p+1$ 时，有\[k\cdot 2^n+1\equiv -2k+1\pmod 5,\]于是当 $k\equiv 3\pmod 5$ 时，有 $5\mid k\cdot 2^n+1$．
（ii）$m=2p$ 时，有\[k\cdot 2^n+1\equiv 2k+1\pmod{13},\]于是当 $k\equiv 6\pmod {13}$ 时，有 $13\mid k\cdot 2^n+1$．
情形四 当 $n=6m+5$ 时，利用立方和公式进行质因数分解可得\[\begin{split}2^{18}-1&=3^3\cdot 7\cdot 19\cdot 73,\\ 2^{18}+1&=5\cdot 13\cdot 37\cdot 109,\end{split}\]于是
（i）$m=3p$ 时，有\[k\cdot 2^n+1\equiv 32k+1\equiv 13k+1\pmod {19},\]于是当 $13k\equiv -1\pmod{19}$ 时，有 $19\mid k\cdot 2^n+1$．
（ii）$m=3p+1$ 时，有\[k\cdot 2^n+1\equiv 2048k+1\equiv 4k+1\pmod{73},\]于是当 $4k\equiv -1\pmod{73}$ 时，有 $73\mid k\cdot 2^n+1$．
（iii）$m=3p+2$ 时，若 $p=2q$，则有\[k\cdot 2^n+1\equiv 131072k+1\equiv 18k+1\pmod{37},\]于是当 $18k\equiv -1\pmod{37}$ 时，有 $37\mid k\cdot 2^n+1$；
若 $p=2q+1$，则有\[k\cdot 2^n+1\equiv -131072k+1\equiv -54k+1\pmod{109},\]于是当 $54k\equiv 1\pmod{109}$ 时，有 $109\mid k\cdot 2^n+1$．
综上所述，同余方程组\[\begin{cases}
k&\equiv -1\pmod {3},\\
k&\equiv -1\pmod {7},\\
k&\equiv 3\pmod {5},\\
k&\equiv 6\pmod {13},\\
13k&\equiv -1\pmod {19},\\
4k&\equiv -10\pmod {73},\\
18k&\equiv -1\pmod {37},\\
54k&\equiv 1\pmod {109},\\
\end{cases}\]的解符合要求．根据中国剩余定理，该同余方程组的解 $k\equiv k_0\pmod {M}$，其中\[M=3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73\cdot 109=7635497415,\]因此我们得到了一个小于 $7635497415$ 的数 $k$．
（i）$m=2p+1$ 时，有\[k\cdot 2^n+1\equiv -2k+1\pmod 5,\]于是当 $k\equiv 3\pmod 5$ 时，有 $5\mid k\cdot 2^n+1$．
（ii）$m=2p$ 时，有\[k\cdot 2^n+1\equiv 2k+1\pmod{13},\]于是当 $k\equiv 6\pmod {13}$ 时，有 $13\mid k\cdot 2^n+1$．
（i）$m=3p$ 时，有\[k\cdot 2^n+1\equiv 32k+1\equiv 13k+1\pmod {19},\]于是当 $13k\equiv -1\pmod{19}$ 时，有 $19\mid k\cdot 2^n+1$．
（ii）$m=3p+1$ 时，有\[k\cdot 2^n+1\equiv 2048k+1\equiv 4k+1\pmod{73},\]于是当 $4k\equiv -1\pmod{73}$ 时，有 $73\mid k\cdot 2^n+1$．
（iii）$m=3p+2$ 时，若 $p=2q$，则有\[k\cdot 2^n+1\equiv 131072k+1\equiv 18k+1\pmod{37},\]于是当 $18k\equiv -1\pmod{37}$ 时，有 $37\mid k\cdot 2^n+1$；
若 $p=2q+1$，则有\[k\cdot 2^n+1\equiv -131072k+1\equiv -54k+1\pmod{109},\]于是当 $54k\equiv 1\pmod{109}$ 时，有 $109\mid k\cdot 2^n+1$．
综上所述，同余方程组\[\begin{cases}
k&\equiv -1\pmod {3},\\
k&\equiv -1\pmod {7},\\
k&\equiv 3\pmod {5},\\
k&\equiv 6\pmod {13},\\
13k&\equiv -1\pmod {19},\\
4k&\equiv -10\pmod {73},\\
18k&\equiv -1\pmod {37},\\
54k&\equiv 1\pmod {109},\\
\end{cases}\]的解符合要求．根据中国剩余定理，该同余方程组的解 $k\equiv k_0\pmod {M}$，其中\[M=3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73\cdot 109=7635497415,\]因此我们得到了一个小于 $7635497415$ 的数 $k$．
答案
解析
备注
