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

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

$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 では成り立つよね（必要条件）

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

ここで候補と書いたのは、あくまでこの $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}$ として

よって答えは $7$ （回答終わり）

以上、こんな感じです。