必要条件で絞り込む【整数問題】

質問箱でこんな問題が送られてきたので解いてみます。

\(n\) を自然数とする。整数 \(19^n + (-1)^{n-1} 2^{4n-3}\) のすべてを割り切る素数を求めよ。

86 東工大?

うーん、これ何からやればいいのだろう?というときは

とりあえず何よりも実験

です。まずは \(n = 1\) などのカンタンな値を代入して計算し、この整数の挙動を確認していきます。

\(a_n = 19^n + (-1)^{n-1} 2^{4n-3}\) とする。

\(n = 1\) のとき、 \(a_1 = 21 = 3 \cdot 7\)
\(n = 2\) のとき、 \(a_2 = 329 = 7 \cdot 47\)

で、この時点で共通する素因数が \(7\) しかないことがわかります。

すべての n で成り立つということは、少なくとも n = 1, 2 では成り立つよね(必要条件)

今回のタイトルに必要条件で絞り込むと書きましたが、つまりこういうことです。

必要条件で絞り込む

求める素数は、任意の $n$ に対して $a_n$ を割り切る素数であるから、少なくとも $n = 1, 2$ に対して $a_1, a_2$ をそれぞれ割り切る素数である。ということはその候補には $7$ しかない。

ここで候補と書いたのは、あくまでこの \(7\) という値は \(n = 1, 2\) でしか成り立つことを確認していないからです。この候補 \(7\) が実際に任意の \(n\) に対して条件をみたすことを確認する必要があり、これを一般に十分性の確認といいます。

さて、以上の考察を踏まえて、今回は合同式を使って十分性の確認をしてしまおうと思います。

回答例

\(a_n = 19^n + (-1)^{n-1} 2^{4n-3}\) とする。

\(n = 1\) のとき、 \(a_1 = 21 = 3 \cdot 7\)
\(n = 2\) のとき、 \(a_2 = 329 = 7 \cdot 47\)

よって求める素数は \(7\) 以外ありえない。以下この \(7\) が \(a_n\) を割り切ることを示す。合同式は \(\mod{7}\) として

\begin{align*}
19^n + (-1)^{n-1} 2^{4n-3} & \equiv 5^n + (-1)^{n-1} \cdot 2^{3(n-1)} \cdot 2^n \\
& \equiv 5^n + (-1)^{n-1} \cdot 2^n \\
& = 5^n + 6^{n-1} \cdot 2^{n-1} \cdot 2 \\
& = 5^n + 12^{n-1} \cdot 2 \\
& \equiv 5^n + 5^{n-1} \cdot 2 \\
& = 5^{n-1}(5 + 2) \\
& \equiv 0
\end{align*}

よって答えは \(7\) (回答終わり)

以上、こんな感じです。

ポイント

実験をして必要条件から解の候補を絞り、十分性を確認することで解を求める

この記事を書いた人

サトゥー

東大学際情報学府M1。情報科学と教養の海に溺れています。面白いことをやるのがすきです。