自分で得点を指定できる問題 – 1995年京大 後期 文系 数学 第4問
今回取り上げる、 1995年京大 後期 文系 数学 第4問 は、自分で得点を指定できるという、キャッチーな問題です。とはいってもふざけているわけではなく、実態は剰余類に関する問題です。
問題文は以下の通りです。
自然数 n の関数 f(x) 、 g(x) を
\text{ } f(n) = n を7で割った余り
\begin{aligned}
& \text{ } g(n) = 3f( \sum_{k=1}^7 k^n )
\end{aligned}
によって定める。
(1) すべての自然数 n に対して f(n^7)=f(n) を示せ。
(2) あなたが好きな自然数 n を一つ決めて g(n) を求めよ。
その g(n) の値をこの設問(2)におけるあなたの得点とする。
小問１の解法
関数 f(n) の性質
f(n) は7の剰余類ですが、まず剰余類の性質をおさらいします。
剰余類の最も重要な性質は、それが足し算と掛け算に閉じていて、しかも整数におけるそれら演算の自然な拡張になっているところです。すなわち、 a,b を整数とするとき、以下の等式が成り立ちます。
\begin{aligned}
f(a \pm b) & = f(f(a) \pm f(b)) \\
f(ab) & = f(f(a)f(b)) \\
\end{aligned}この性質のおかげで、本問では0から6までの7つの整数の足し算、引き算、及び掛け算（の結果を7で割った余り）だけを考えれば良いことになります。
演算結果の書き下しによる解法
剰余類の性質を踏まえたとき、小問1はすべての n と言っても、 n= 1,2,・・,6について、以下が証明できれば十分です（ n=0 のときは明らか）。
n^7 \equiv n \mod 7
これはいわゆるフェルマーの小定理です。これを証明して見せろというのはハードル高いですが、7の時だけ証明すればよいので、実際に計算して見せるというのも有りだと思います。 以下のとおりです。
\begin{aligned}
1^7 & = 1 \\
2^7 &= (2^3)^2 \cdot 2 = 8^2 \cdot2 \\
& \equiv 1^2 \cdot 2\equiv 2 \mod 7 \\
3^7 &= (3^3)^2 \cdot 3 \equiv 27^2 \cdot 3 \\
& \equiv 6^2 \cdot 3 \equiv 36 \cdot 3 \equiv 1 \cdot 3 \equiv 3 \mod 7 \\
4^7 &= (2^7)^2 \equiv 2^2 \equiv 4 \mod 7 \\
5^7 &= (5^2)^3 \cdot 5 = 25^3 \cdot 5 \\
& \equiv 4^3 \cdot 5 \equiv64 \cdot 5 \equiv 1 \cdot 5 \equiv 5 \mod 7 \\
6^7 &= 2^7 \cdot 3^7 \equiv 2 \cdot 3 \equiv 6 \mod 7
\end{aligned}フェルマーの小定理の証明
ちなみに、フェルマーの小定理の証明は、以下の通りです。Wikipediaを参考にしました。
素数 p と、任意の自然数 m,n に対し、二項定理により以下の等式が成り立ちます。
\begin{aligned}
& (m+n)^p \\
& = m^p + \sum_{k=1}^{p-1} {} _p \mathrm{C} _k m^k n^{p-k} + n^p
\end{aligned}ところで、 {} _p \mathrm{C} _k = \frac{p!}{k!(p-k)!} ですが、 p は素数のため、分母のどの数字によっても約されることはありません。したがって、 {} _p \mathrm{C} _k は p を素因数にもつ、すなわち p で割り切れるので、
(m+n)^p \equiv m^p + n^p \mod p
が成り立ちます。
以上により、
\begin{aligned}
& n^p = \{ 1 + (n-1) \}^p \\
& \text{ } \equiv 1^p + (n-1)^p \\
& \text{ } \equiv 1^p + 1^p + (n-2)^p \\
& \text{ } \equiv \overbrace{ 1^p + 1^p + \cdots+ 1^p }^{ n \text{個} } \\
& \text{ } \equiv n \mod p
\end{aligned}が成り立ちます。
実に水際立った証明です。この証明を最初に考えた人（ライプニッツか？）は、天才だと思います。
フェルマーの小定理それ自体を覚えておく必要はありませんが、その証明手法は、剰余類の問題でべき乗を処理するのに使えるので、頭の片隅に留めておくと便利です。