トップ› 東京大学› 2007年› 文系第3問

東京大学 2007年文系第3問解説

方針・初手

正の整数の下2桁を求めることは、その数を $100$ で割った余りを求めることと同義である。

合同式を用いて、$5m^4 \pmod{100}$ がどのような値をとるかを調べる。式に係数 $5$ が含まれていることに着目し、二項定理を利用して $m$ の一の位（$10$ で割った余り）のみに依存することを示す方針か、あるいは剰余の性質を用いて式全体を $5$ で割り、法を $20$ に落としてから中国剰余定理の考え方を用いる方針が有効である。

解法1

求める数は、$5m^4$ を $100$ で割った余りである。

任意の正の整数 $m$ は、ある $0$ 以上の整数 $q$ と、$0 \le r \le 9$ を満たす整数 $r$ を用いて、$m = 10q + r$ と表すことができる。

このとき、$5m^4$ を二項定理を用いて展開すると、以下のようになる。

$$ \begin{aligned} 5m^4 &= 5(10q + r)^4 \\ &= 5(10000q^4 + 4000q^3r + 600q^2r^2 + 40qr^3 + r^4) \\ &= 50000q^4 + 20000q^3r + 3000q^2r^2 + 200qr^3 + 5r^4 \\ &= 100(500q^4 + 200q^3r + 30q^2r^2 + 2qr^3) + 5r^4 \end{aligned} $$

上式の括弧内は整数であるため、法を $100$ とする合同式において次が成り立つ。

$$ 5m^4 \equiv 5r^4 \pmod{100} $$

これにより、$5m^4$ の下2桁は、$m$ の一の位の数 $r$ にのみ依存することがわかる。したがって、各 $r = 0, 1, 2, \dots, 9$ について $5r^4$ を計算し、その下2桁を調べれば十分である。

$r = 0$ のとき、$5 \cdot 0^4 = 0$（下2桁は $0$）
$r = 1$ のとき、$5 \cdot 1^4 = 5$（下2桁は $5$）
$r = 2$ のとき、$5 \cdot 2^4 = 80$（下2桁は $80$）
$r = 3$ のとき、$5 \cdot 3^4 = 405 \equiv 5 \pmod{100}$（下2桁は $5$）
$r = 4$ のとき、$5 \cdot 4^4 = 1280 \equiv 80 \pmod{100}$（下2桁は $80$）
$r = 5$ のとき、$5 \cdot 5^4 = 3125 \equiv 25 \pmod{100}$（下2桁は $25$）
$r = 6$ のとき、$5 \cdot 6^4 = 6480 \equiv 80 \pmod{100}$（下2桁は $80$）
$r = 7$ のとき、$5 \cdot 7^4 = 12005 \equiv 5 \pmod{100}$（下2桁は $5$）
$r = 8$ のとき、$5 \cdot 8^4 = 20480 \equiv 80 \pmod{100}$（下2桁は $80$）
$r = 9$ のとき、$5 \cdot 9^4 = 32805 \equiv 5 \pmod{100}$（下2桁は $5$）

調べた結果より、下2桁として現れる数は $0, 5, 25, 80$ である。

解法2

合同式の法を $100$ とする。$5m^4 \equiv x \pmod{100}$ を満たす整数 $x$ （$0 \le x \le 99$）を求める。

$100$ は $5$ の倍数であるため、$5m^4 - x$ が $100$ の倍数となるためには $x$ も $5$ の倍数でなければならない。そこで、$x = 5y$ （$y$ は $0 \le y \le 19$ を満たす整数）とおく。

$$ 5m^4 \equiv 5y \pmod{100} $$

この合同式の両辺と法を $5$ で割ることで、以下の式を得る。

$$ m^4 \equiv y \pmod{20} $$

ここで、法 $20$ を互いに素な $4$ と $5$ に分解し、$m^4$ の法 $4$ および法 $5$ における余りを調べる。

まず、法 $4$ について考える。 $m$ が偶数のとき、$m = 2k$ とおくと $m^4 = 16k^4 \equiv 0 \pmod 4$ である。 $m$ が奇数のとき、$m = 2k+1$ とおくと $m^2 = 4k^2+4k+1 \equiv 1 \pmod 4$ より、$m^4 \equiv 1^2 \equiv 1 \pmod 4$ である。

次に、法 $5$ について考える。 $m$ が $5$ の倍数のとき、$m^4 \equiv 0 \pmod 5$ である。 $m$ が $5$ の倍数でないとき、$m$ と $5$ は互いに素であるため、フェルマーの小定理より $m^4 \equiv 1 \pmod 5$ である。

これらを組み合わせて、$y$ の値を場合分けして求める。

(i) $m$ が偶数かつ $5$ の倍数のとき

$y \equiv 0 \pmod 4$ かつ $y \equiv 0 \pmod 5$ である。 $4$ と $5$ は互いに素であるから、$y \equiv 0 \pmod{20}$ となる。 $0 \le y \le 19$ より $y = 0$ であり、$x = 5 \cdot 0 = 0$ である。

(ii) $m$ が偶数かつ $5$ の倍数でないとき

$y \equiv 0 \pmod 4$ かつ $y \equiv 1 \pmod 5$ である。この連立合同式を満たす $0 \le y \le 19$ の範囲の整数は、$y = 16$ である。よって、$x = 5 \cdot 16 = 80$ である。

(iii) $m$ が奇数かつ $5$ の倍数のとき

$y \equiv 1 \pmod 4$ かつ $y \equiv 0 \pmod 5$ である。この連立合同式を満たす $0 \le y \le 19$ の範囲の整数は、$y = 5$ である。よって、$x = 5 \cdot 5 = 25$ である。

(iv) $m$ が奇数かつ $5$ の倍数でないとき

$y \equiv 1 \pmod 4$ かつ $y \equiv 1 \pmod 5$ である。 $4$ と $5$ は互いに素であるから、$y \equiv 1 \pmod{20}$ となる。 $0 \le y \le 19$ より $y = 1$ であり、$x = 5 \cdot 1 = 5$ である。

以上（i）から（iv）より、求める下2桁の数は $0, 5, 25, 80$ である。