问题及解答

设 $k$ 是正整数. 证明 $\mathrm{gcd}(k,2^n+3^n+6^n-1)=1$ 对所有正整数 $n$ 成立当且仅当 $k=1$.

Remark:

问题来源: 

原文:

Let $k$ be a positive integer. Prove that $\mathrm{gcd}(k,2^n+3^n+6^n-1)=1$ for every positive integer $n$ if and only if $k=1$.

[Hint]:  Show that every prime must divide $2^n+3^n+6^n-1$ for some natural n. Consider cases when $p=2,3$ and $ > 3$. When $p > 3$, you may want to particularly look at $6(2^n+3^n+6^n-1)$, and to choose a value of $n$ which will allow you to use $\mathrm{F}\ell\mathrm{T}$.

Remark.  这里 $\mathrm{F}\ell\mathrm{T}$  指 Fermat Little Theorem.

首先 $k\neq 2$, 因为 $2^n+3^n+6^n-1$ 是偶数.

充分性是显然的. 下证必要性. 

假设 $\mathrm{gcd}(k,2^n+3^n+6^n-1)=1$ 对所有 $n\in\mathbb{N}$ 成立. 

若 $k\neq 1$, 则 $k$ 是奇数, 不妨设 $k=p_1 p_2 \cdots p_s$. 即存在这些素数 $p_i$, $i=1,2,\ldots,s$, 使得

\[p_i\not| 2^n+3^n+6^n-1,\quad\forall\ n\in\mathbb{N}.\]

这个命题的反面即为:

Claim. 任给素数 $p$, 存在某个 $n\in\mathbb{N}$, 使得 $p|(2^n+3^n+6^n-1)$.

Pf.  记 $f(n)=2^n+3^n+6^n-1$. $p=2$ 时是显然的. 当 $p=3$ 时, $p|f(4)$. 当 $p=5$ 时, $p|f(5)$

下设 $p > 6$.

考虑 $g(n)=6f(n)$, 即

\[
\begin{split}
g(n)&=2\cdot 3\cdot 2^n+2\cdot 3\cdot 3^n+2\cdot 3\cdot 6^n-6\\
&=3\cdot(2^{n+1}-1)+2\cdot(3^{n+1}-1)+(6^{n+1}-1)
\end{split}
\]

根据 Fermat 小定理(见问题2296), 对于 $0 < a < p$, 有 $a^{p-1}\equiv 1\pmod p$. 于是, 若取 $n=p-2$, 则有

\[
p | (2^{n+1}-1),\quad p | (3^{n+1}-1),\quad p | (6^{n+1}-1),\quad
\]

因此, $p| g(p-2)$, 从而 $p| f(p-2)$.