求证：对于每个正整数 $n$，都存在满足下面三个条件的质数 $p$ 和整数 $m$：（1）$p\equiv 5\left( \bmod 6 \right)$；（2）$p\nmid n$；（3）$n\equiv {{m}^{3}}\left( \bmod p \right)$ 。
【难度】
【出处】
2010第9届CGMO试题
【标注】
【答案】
略
【解析】
证法1：先证明：模6余5的质数有无穷多个。若不然，则模6余5的质数只有有限多个，设它们从小到大依次为 ${{p}_{1}}\text{,}{{p}_{2}}\text{,}\cdots\text{,}{{p}_{r}}$ 。考虑数 $6{{p}_{1}}{{p}_{2}}\cdots {{p}_{r}}-1$ 。因其模6余5，所以它的质因子模6余1或5．特别地，它有一个质因子 $q$ 模6余5．但由 ${{p}_{r}}\nmid \left(6{{p}_{1}}{{p}_{2}}\cdots {{p}_{r}}-1 \right)\left(s\text{=}1\text{,}2\text{,}\cdots \text{,}r \right)$，得 $q\notin \left\{ {{p}_{1}}\text{,}{{p}_{2}}\text{,}\cdots\text{,}{{p}_{r}} \right\}$，矛盾。 其次，由于模6余5的质数有无穷多个，其中必有不整除 $n$ 的质数，设其中一个为 $p\text{=}6k+5$，则条件（1）、（2）成立。取 $m\text{=}{{n}^{4k+3}}$，由费马小定理 ${{m}^{3}}\text{=}{{\left({{n}^{4k+3}} \right)}^{3}}\text{=}{{\left( {{n}^{6k+4}} \right)}^{2}}n\equiv n\left( \bmod p \right)$，这样的 $p$ 和 $m$ 即满足题目条件。 证法2：当 $n\text{=}1$ 时，取 $p\text{=}5$，$m\text{=}1$；当 $n\text{=}2$ 时，取 $p\text{=}5$，$m\text{=}3$ 。易验证 $p$ 和 $m$ 满足题目条件。 下面假设 $n\ge3$ 。由 ${{\left( n-1 \right)}^{3}}-n$ > $0$ 及 ${{\left( n-1 \right)}^{3}}-n\equiv\left( n-1 \right)-n\equiv 5\left( \bmod 6 \right)$，知 ${{\left( n-1\right)}^{3}}-n$ 必有一个模6余5的质因子。取 $p$ 为这个质因子，并取 $m\text{=}n-1$ 。下证这样的 $p$ 和 $m$ 满足条件。由 $p$、$m$ 的取法知条件（1）、（3）成立。由 $\left({{m}^{3}}-n\text{,}n \right)\text{=}\left( {{m}^{3}}\text{,}n\right)\text{=}\left( {{\left( n-1 \right)}^{3}}\text{,}n \right)\text{=}\left(1\text{,}n \right)\text{=}1$，知 $p\nmid n$，即条件（2）成立。因此，存在满足题目条件的 $p$ 和 $m$ 。
答案
解析
备注
