剰余類の威力を体感せよ！ 1986年東工大 数学 第1問
1986年東工大 数学 第1問 は整数列の問題ですが、剰余類を利用すると鮮やかに解くことが出来ます。問題文は以下のとおりです。
整数 a_n =19^n + (-1)^{n-1} 2^{4n-3} \text{ } ( n=1,2,3,\cdots ) のすべてを割り切る素数を求めよ．
なかなか強面の問題です。一筋縄では行かない気配を漂わせていますが、どうでしょうか。早速見ていきましょう。
なお、以下の内容は、東工大が公表したものではありません。
1986年東工大 数学 第1問 の解法
a_n の値を実際に求めて、傾向をつかむ
本問のような整数列の問題では、数列の最初のいくつかを実際に計算してみて、その傾向をつかむというのが、王道のアプローチです。では計算してみましょう。
\begin {aligned}
a_1 &= 19^1 +(-1)^02^1 = 19 + 2 = 21 = 3 \cdot 7 \\
a_2 &= 19^2 +(-1)^12^5 = 361 - 32 = 329 = 7 \cdot 47
\end{aligned}a_1,a_2 の共通素因数が7であることがわかりましたので、すべての a_n,n=1,2,\cdots を割り切る素数が在るとしたら、それは7しかあり得ません。
したがって、題意は以下のように言い換えられます。
整数 a_n =19^n + (-1)^{n-1} 2^{4n-3} \text{ } ( n=1,2,3,\cdots ) が7で割り切れることを証明せよ．
この手の、割り切れることを証明せよ的な問題では、剰余類が無類の力を発揮します。本稿では、これを使って解いていきます。
剰余類のおさらい
自然数 p を法とする剰余類とは、簡単に言うと整数を p で割った余りのことで、すべての整数（負の整数でもOK）を、余りが同じならおなじものとして扱います。本問では7を法とする剰余類を考えるので、曜日のアナロジーがぴったり来ます。1日が日曜日なら8日も日曜日。日付を7で割った余りが同じなら同じ曜日になりますが、これが正に剰余類です。
2つの整数 a,b を p で割った余りが等しいとき、以下のように表記します。
a \equiv b \mod p
たとえば、
8 \equiv 1 \mod 7
です。
なぜ剰余類が便利かというと、それが足し算、引き算、掛け算に閉じているからです。すなわち、2数の演算結果を p で割った余りは、それぞれの余りの演算結果をpで割った余りに等しくなります。
表現がとても回りくどくなっていますが、具体例を見ると明らかだと思います。以下のとおりです。
\begin{aligned}
8+15 & = 23 \equiv 2 \mod 7 \\
8 + 15 & \equiv1+1 \equiv 2 \mod7 \\
8-15 & = -7 \equiv 0 \mod 7 \\
8 - 15 & \equiv1-1 \equiv 0 \mod7 \\
8 \times 15 & = 120 \equiv 1 \mod 7 \\
8 \times 15 & \equiv 1 \times 1 \equiv 1 \mod 7
\end{aligned}要は、余りの計算だけすれば良いので、本問のようにごちゃごちゃ計算させられるような場合には、非常に重宝します。
a_n が7で割り切れることの証明
剰余類を使って、実際に計算します。
\begin{aligned}
a_n &=19^n + (-1)^{n-1} 2^{4n-3} \\
& = 19^n + (-1)^{n-1} 2^{4(n-1) +1} \\
& =19^n + 2(-16)^{n-1}
\end{aligned}ですが、
\begin{aligned}
19 & \equiv 5 \mod 7 \\
-16 & = -21+5 \equiv 5 \mod 7
\end{aligned}なので、これを代入して
\begin{aligned}
a_n & \equiv 5^n + 2 \cdot 5^{n-1} \\
& \equiv (5+2) 5^{n-1} \equiv 0 \mod 7
\end{aligned}これはまさに、 a_n が7で割り切れるという主張にほかなりません。
ゆえに、すべての a_n を割り切る素数は7しか無いことが示せました。
発展
p が素数の時には、剰余類は、掛け算の逆演算としての割り算にも閉じます。すなわち、任意の a \not\equiv 0 に対し、
ab \equiv 1 \mod p
を満たす b が、 \mod p が同じものを同一視するとき、ただ1種類だけ存在します。つまり、 a の「逆数」が一意に決まります。
たとえば、5の逆数は3です。
5 \times 3 = 15 \equiv 1 \mod 7
このことは高校の履修範囲を超えますが、知っておくと、剰余類における逆数を求める必要があるときに、実際に計算してみようと思いつけます。
解法のポイント
ググってみると、本問の解法には数学的帰納法を適用したり、二項定理を使ったりするものを見いだせますが、本稿のように剰余類を利用すると、より簡単に結果を得られます。
以上のように剰余類は、素数で割り切れるとか、素数で割った余りがどうとか言った問題に対して、強力なツールになりますので、ぜひ使用法をマスターしてください。