トップ› 東京大学› 1974年› 文系第1問

東京大学 1974年文系第1問解説

方針・初手

$f_p(n)$ は $n^p$ を $10$ 進法で書いたときの $1$ の位の数であるから、$n^p$ を $10$ で割ったときの余りに等しい。すなわち、合同式を用いて法を $10$ としたときの $n^p \pmod{10}$ を考えればよい。

すべての自然数 $n$ は、$10$ で割った余りによって $n \equiv k \pmod{10}$ （$k=0, 1, 2, \cdots, 9$）と表せるため、$1$ の位の数は $n$ の $1$ の位の数のみに依存する。合同式の性質や因数分解を活用して法則性や周期性を見つけることがカギとなる。

解法1

(1)

任意の自然数 $n$ を $10$ で割った余りを $k$ （$k=0, 1, 2, \dots, 9$）とする。

$n \equiv k \pmod{10}$ より、$n^2 \equiv k^2 \pmod{10}$ が成り立つ。

各 $k$ について、$k^2$ を $10$ で割った余りを計算すると以下のようになる。

$$ \begin{aligned} 0^2 &= 0 \equiv 0 \pmod{10} \\ 1^2 &= 1 \equiv 1 \pmod{10} \\ 2^2 &= 4 \equiv 4 \pmod{10} \\ 3^2 &= 9 \equiv 9 \pmod{10} \\ 4^2 &= 16 \equiv 6 \pmod{10} \\ 5^2 &= 25 \equiv 5 \pmod{10} \\ 6^2 &= 36 \equiv 6 \pmod{10} \\ 7^2 &= 49 \equiv 9 \pmod{10} \\ 8^2 &= 64 \equiv 4 \pmod{10} \\ 9^2 &= 81 \equiv 1 \pmod{10} \end{aligned} $$

したがって、$f_2(n)$ の取る値は $0, 1, 4, 5, 6, 9$ である。

(2)

$f_5(n) = f_1(n)$ であることを示すには、すべての自然数 $n$ に対して $n^5 \equiv n \pmod{10}$ 、すなわち $n^5 - n$ が $10$ の倍数であることを示せばよい。

$n^5 - n$ を因数分解する。

$$ \begin{aligned} n^5 - n &= n(n^4 - 1) \\ &= n(n^2 - 1)(n^2 + 1) \\ &= (n-1)n(n+1)(n^2+1) \end{aligned} $$

ここで、$(n-1)n$ は連続する $2$ つの整数の積であるため偶数である。よって、$n^5 - n$ は $2$ の倍数である。

次に、$n^2 + 1 = (n^2 - 4) + 5$ と変形して代入する。

$$ \begin{aligned} n^5 - n &= (n-1)n(n+1)\{(n^2 - 4) + 5\} \\ &= (n-1)n(n+1)(n-2)(n+2) + 5(n-1)n(n+1) \\ &= (n-2)(n-1)n(n+1)(n+2) + 5(n-1)n(n+1) \end{aligned} $$

第1項の $(n-2)(n-1)n(n+1)(n+2)$ は連続する $5$ つの整数の積であるから、$5$ の倍数である。また、第2項の $5(n-1)n(n+1)$ も $5$ を因数に持つため $5$ の倍数である。よって、$n^5 - n$ は $5$ の倍数である。

$2$ と $5$ は互いに素であるから、$n^5 - n$ は $2 \times 5 = 10$ の倍数である。ゆえに $n^5 \equiv n \pmod{10}$ が成り立ち、$f_5(n) = f_1(n)$ が示された。

(3)

(2)より、任意の自然数 $n$ に対して $n^5 \equiv n \pmod{10}$ が成り立つ。

両辺に $n^4$ を掛けると $n^9 \equiv n^5 \equiv n \pmod{10}$ となる。これを繰り返すことで、自然数 $k$ に対して $n^{4k+1} \equiv n \pmod{10}$ が成り立つことがわかる。したがって、任意の自然数 $p$ に対して、指数が $4$ 増えるごとに $1$ の位は一致し、$n^{p+4} \equiv n^p \pmod{10}$ が成り立つ。

これを用いると、$n^{100}$ は以下のように次数を下げることができる。

$$ n^{100} = n^{4 \times 24 + 4} \equiv n^4 \pmod{10} $$

よって、$f_{100}(n) = f_4(n)$ となる。

$n^4 = (n^2)^2$ であるから、$f_4(n)$ は $n^2$ をさらに $2$ 乗した数の $1$ の位に等しい。すなわち、（1）で求めた $f_2(n)$ の値をそれぞれ $2$ 乗して $1$ の位を調べればよい。

(1)より、$f_2(n)$ の取る値は $0, 1, 4, 5, 6, 9$ であるから、これらを $2$ 乗した数の $1$ の位は以下のようになる。

$$ \begin{aligned} 0^2 &= 0 \equiv 0 \pmod{10} \\ 1^2 &= 1 \equiv 1 \pmod{10} \\ 4^2 &= 16 \equiv 6 \pmod{10} \\ 5^2 &= 25 \equiv 5 \pmod{10} \\ 6^2 &= 36 \equiv 6 \pmod{10} \\ 9^2 &= 81 \equiv 1 \pmod{10} \end{aligned} $$

以上より、$f_{100}(n)$ の取る値は $0, 1, 5, 6$ である。

解法2

（2）の別解

フェルマーの小定理を用いる。フェルマーの小定理より、素数 $p$ と任意の整数 $a$ に対して $a^p \equiv a \pmod p$ が成り立つ。

$p=5$ とすると、任意の自然数 $n$ に対して以下が成り立つ。

$$ n^5 \equiv n \pmod 5 $$

よって、$n^5 - n$ は $5$ の倍数である。

同様に $p=2$ とすると、$n^2 \equiv n \pmod 2$ が成り立つ。これを用いると、

$$ \begin{aligned} n^5 - n &= n(n^4-1) \\ &= n(n^2-1)(n^2+1) \\ &\equiv n(n-1)(n+1) \pmod 2 \\ &\equiv (n^2-n)(n+1) \pmod 2 \\ &\equiv (n-n)(n+1) \pmod 2 \\ &\equiv 0 \pmod 2 \end{aligned} $$

よって、$n^5 - n$ は $2$ の倍数でもある。

$2$ と $5$ は互いに素であるから、$n^5 - n$ は $10$ の倍数である。ゆえに $n^5 \equiv n \pmod{10}$ であり、$f_5(n) = f_1(n)$ が成り立つ。

解法3

（2）の別解

$n$ の $1$ の位の数のみに着目すればよいため、$n \equiv 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \pmod{10}$ の全事象について、$n^5 \pmod{10}$ を直接計算して確認する。

$$ \begin{aligned} 0^5 &= 0 \equiv 0 \pmod{10} \\ 1^5 &= 1 \equiv 1 \pmod{10} \\ 2^5 &= 32 \equiv 2 \pmod{10} \\ 3^5 &= 243 \equiv 3 \pmod{10} \\ 4^5 &= 1024 \equiv 4 \pmod{10} \\ 5^5 &= 3125 \equiv 5 \pmod{10} \\ 6^5 &= 7776 \equiv 6 \pmod{10} \\ 7^5 &= 16807 \equiv 7 \pmod{10} \\ 8^5 &= 32768 \equiv 8 \pmod{10} \\ 9^5 &= 59049 \equiv 9 \pmod{10} \end{aligned} $$

すべての場合において $n^5 \equiv n \pmod{10}$ が成り立つことが確認できた。したがって、あらゆる自然数 $n$ に対して $f_5(n) = f_1(n)$ が成り立つ。

解説

ある整数の $1$ の位の数を求める問題は、$10$ を法とする合同式で考えるのが定石である。すべての自然数は $10$ で割った余りによって $10$ パターンに分類されるため、有限回の計算で法則性や周期性を見つけることができる。

（2）の証明では、合同式による全探索（解法3）でも十分証明として成立するが、解法1のように因数分解を用いて連続整数の積の性質を利用したり、解法2のようにフェルマーの小定理を用いることでより汎用的な論証が可能になる。（3）は（2）の結果から指数が $4$ 周期で循環することを利用し、次数を大幅に下げるのがポイントである。