解説

方針・初手

$12^2$ と $11$ を $19$ で割った余りに注目する。実際、

$$ 12^2=144\equiv 11 \pmod{19}

$$

であるから、$12^{2n-1}$ を $11^{n-1}$ を含む形に直すと、全体に $19$ の倍数が現れる。

解法1

$19$ を法として考える。

まず、

$$ 12^2=144=19\cdot 7+11

$$

より、

$$ 12^2\equiv 11 \pmod{19}

$$

である。

$n$ は自然数であり、式 $12^{2n-1}$ が現れているので $n\geqq 1$ とする。このとき、

$$ 12^{2n-1}=12(12^2)^{n-1}

$$

であるから、

$$ 12^{2n-1}\equiv 12\cdot 11^{n-1}\pmod{19}

$$

となる。

したがって、

$$ \begin{aligned} 11^{n+1}+12^{2n-1} &\equiv 11^{n+1}+12\cdot 11^{n-1} \pmod{19}\\ &=11^{n-1}(11^2+12)\\ &=11^{n-1}(121+12)\\ &=11^{n-1}\cdot 133\\ &=11^{n-1}\cdot 19\cdot 7. \end{aligned}

$$

右辺は $19$ の倍数である。

よって、

$$ 11^{n+1}+12^{2n-1}\equiv 0\pmod{19}

$$

であるから、$11^{n+1}+12^{2n-1}$ は $19$ で割り切れる。

解法2

数学的帰納法で示す。

命題 $P(n)$ を

$$ 11^{n+1}+12^{2n-1}\text{ は }19\text{ で割り切れる}

$$

とする。

まず $n=1$ のとき、

$$ 11^{2}+12^{1}=121+12=133=19\cdot 7

$$

であるから、$P(1)$ は成り立つ。

次に、ある自然数 $k$ について $P(k)$ が成り立つと仮定する。すなわち、

$$ 11^{k+1}+12^{2k-1}

$$

は $19$ で割り切れるとする。

このとき、

$$ \begin{aligned} &\left(11^{k+2}+12^{2k+1}\right)-11\left(11^{k+1}+12^{2k-1}\right)\\ &=11^{k+2}+12^{2k+1}-11^{k+2}-11\cdot 12^{2k-1}\\ &=12^{2k-1}(12^2-11)\\ &=12^{2k-1}(144-11)\\ &=12^{2k-1}\cdot 133\\ &=12^{2k-1}\cdot 19\cdot 7. \end{aligned}

$$

これは $19$ の倍数である。

また、帰納法の仮定より

$$ 11\left(11^{k+1}+12^{2k-1}\right)

$$

も $19$ の倍数である。

したがって、

$$ 11^{k+2}+12^{2k+1}

$$

も $19$ の倍数である。これは $P(k+1)$ が成り立つことを意味する。

以上より、数学的帰納法によって、すべての自然数 $n$ について

$$ 11^{n+1}+12^{2n-1}

$$

は $19$ で割り切れる。

解説

この問題の本質は、

$$ 12^2\equiv 11\pmod{19}

$$

を見抜くことである。指数 $2n-1$ は奇数なので、

$$ 12^{2n-1}=12(12^2)^{n-1}

$$

と変形できる。これにより $12^{2n-1}$ を $11^{n-1}$ と結びつけられる。

合同式で処理する解法1が最短である。数学的帰納法で示す場合も、差を取ると

$$ 12^{2k-1}(12^2-11)

$$

が現れ、同じく $12^2-11=133=19\cdot 7$ を使う形になる。

答え

すべての自然数 $n$ について、

$$ 11^{n+1}+12^{2n-1}

$$

は $19$ で割り切れる。