京大2021年 理系 第6問の問1

を2以上の素数とする。 が素数ならばも素数であることを示せ。

解答例

を合成数とします。
\begin{equation}
n=pq
\end{equation}です。ただし、はなる素数で、とします。
このとき、
\begin{eqnarray}
3^n -2^n &=& 3^{pq} -2^{pq} \\
&=& (3^p -2^p) \left( 3^{p(q -1)} +3^{p(q -2)} \cdot 2^p + \cdots + 3^p \cdot 2^{p(q -2)} + 2^{p(q -1)} \right)
\end{eqnarray}となります。
\begin{eqnarray}
&& 3^p -2^p \geqq 3^2 -2^2 =5 \\
&& 3^{p(q -1)} +3^{p(q -2)} \cdot 2^p + \cdots + 3^p \cdot 2^{p(q -2)} + 2^p \geqq 3^2 +2^2 =13
\end{eqnarray}なので、 は合成数となります。
つまり、

が素数でないならば、 は素数でない
ことが示されました。

よって、その対偶である

が素数ならば、も素数である
もまた真であることが示されます。(証明終わり)

解説

「 が素数」を表現する術が思い当たりませんでした。
命題を直接証明するのは難しいので、間接的に証明する発想になります。
ある命題が真であるならば、その対偶となる命題は必ず真となることを用いています。
素数ではない数は合成数なので、このような証明が可能になります。
整数が合成数であれば、は因数分解ができる形になります。つまり整数同士の積で表すことができることを示せます。