解説

方針・初手

直接「$3^n-2^n$ が素数ならば $n$ も素数」と示すより、対偶を示す。

すなわち、$n$ が合成数ならば $3^n-2^n$ は素数でないことを示せばよい。合成数 $n$ を $n=ab$ と分解し、差の累乗の因数分解を用いる。

解法1

$n$ が合成数であると仮定する。

このとき、$2$ 以上の整数 $a,b$ を用いて

$$ n=ab

$$

と表せる。

すると

$$ 3^n-2^n=3^{ab}-2^{ab}

$$

である。ここで

$$ 3^{ab}=(3^a)^b,\qquad 2^{ab}=(2^a)^b

$$

だから、

$$ 3^{ab}-2^{ab}=(3^a)^b-(2^a)^b

$$

となる。

差の累乗の公式

$$ X^b-Y^b=(X-Y)(X^{b-1}+X^{b-2}Y+\cdots+XY^{b-2}+Y^{b-1})

$$

を、$X=3^a,\ Y=2^a$ に適用すると、

$$ \begin{aligned} 3^{ab}-2^{ab} &= (3^a-2^a) \left\{ (3^a)^{b-1}+(3^a)^{b-2}2^a+\cdots+3^a(2^a)^{b-2}+(2^a)^{b-1} \right\} \end{aligned} $$

と因数分解できる。

ここで $a\geqq 2$ であるから、

$$ 3^a-2^a\geqq 3^2-2^2=5>1

$$

である。

また、$b\geqq 2$ であり、括弧内は正の整数の和である。特に

$$ (3^a)^{b-1}+(2^a)^{b-1}\geqq 3^a+2^a>1

$$

だから、括弧内も $1$ より大きい整数である。

したがって、$3^n-2^n$ は $1$ より大きい整数同士の積として表されるので、素数ではない。

よって、対偶が示されたため、

$$ 3^n-2^n \text{ が素数ならば } n \text{ も素数}

$$

である。

解説

この問題の核心は、$n$ が合成数のときに指数を $n=ab$ と分解し、$X^b-Y^b$ の形に持ち込むことである。

$3^n-2^n$ の形を見ると、$n$ が積に分解できる場合には

$$ 3^{ab}-2^{ab}=(3^a)^b-(2^a)^b

$$

となり、差の累乗として必ず因数分解できる。このとき、両方の因数が $1$ より大きいことを確認するのが重要である。

単に因数分解できるだけでは、片方の因数が $1$ になる可能性を排除できないため、$a\geqq2,\ b\geqq2$ から各因数が確かに $1$ より大きいことを明記する必要がある。

答え

$n$ が合成数ならば、$n=ab\ (a,b\geqq2)$ と書ける。このとき

$$ 3^n-2^n=(3^a)^b-(2^a)^b

$$

は $3^a-2^a$ を因数にもつ。さらに $3^a-2^a>1$ であり、もう一方の因数も $1$ より大きい整数である。

したがって $3^n-2^n$ は素数でない。よって対偶により、$3^n-2^n$ が素数ならば $n$ も素数である。