問題#A003 ★☆☆☆
$3^{12}-1$の素因数のうち最大のものを求めよ。
《ポイント》
因数分解を駆使して素因数分解を行います。式変形についてはコチラをご覧ください。
また、素因数分解をする際に厄介なのが素数かどうかの判定です。ここでちょっとした事実を紹介します。$N$を自然数とするとき、
「$\sqrt{N}$以下の自然数を約数に持たないならば$N$は素数」
という事実があります。これを知っていると知らないとでは素因数探しのコストが結構変わってきます。
《解答例》
$\begin{align}& \ \ \ \ \ 3^{12}-1 \\
&=(3^6-1)(3^6+1) \\
&=(3^3-1)(3^3+1)(3^2+1)(3^4-3^2+1) \\
&=(3-1)(3^2+3+1)(3+1)(3^2-3+1)(3^2+1)(3^4-3^2+1) \\
&=2 \cdot 13 \cdot 4 \cdot 7 \cdot 10 \cdot 73 \\
&=2^4 \cdot 5 \cdot 7 \cdot 13 \cdot 73 \end{align}$
となるから最大の素因数は$73$である。
（答）$73$
《コメント》
$73$が素数であることは、$\sqrt{73}$以下の自然数$1,2,\cdots,8$で$73$が割り切れないことから明らかです。