トップ› 東京工業大学› 1993年› 理系第4問

東京工業大学 1993年理系第4問解説

方針・初手

多項式 $P(x)$ が整数値をとる条件に関する典型問題である。代表的なアプローチとして以下の2つが考えられる。

1つ目は、階差多項式（差分多項式）を用いた数学的帰納法である。$n$ 次多項式 $P(x)$ に対して、その差分 $Q(x) = P(x+1) - P(x)$ は $n-1$ 次多項式になる。次数を下げることで、帰納法に持ち込むことができる。

2つ目は、連続する整数の積を用いた多項式の表現である。任意の $n$ 次多項式は、二項係数を用いた式表現（あるいは連続する整数の積の和）によって一意に表すことができる。このとき、条件から係数がすべて整数になることを示す。

ここでは、両方の解法を示す。

解法1

$n$ 次の多項式に関する命題「$P(0), P(1), \cdots, P(n)$ が整数ならば、すべての整数 $k$ に対して $P(k)$ は整数である」を、$n$ についての数学的帰納法で証明する。

(I)

$n=1$ のとき $P(x) = ax+b$ （$a, b$ は実数、$a \neq 0$）とおける。条件より、$P(0) = b$ は整数である。また、$P(1) = a+b$ も整数である。このことから、$a = P(1) - b$ であり、整数の差であるから $a$ も整数となる。したがって、任意の整数 $k$ に対して $P(k) = ak+b$ は整数の和となるため、整数である。よって、$n=1$ のときは成立する。

(II)

$n=m$ （$m$ は自然数）のとき、命題が成り立つと仮定する。すなわち、「任意の $m$ 次多項式 $Q(x)$ について、$Q(0), Q(1), \cdots, Q(m)$ が整数ならば、すべての整数 $k$ に対して $Q(k)$ は整数である」と仮定する。

$n=m+1$ のときを考える。 $P(x)$ を $m+1$ 次多項式とし、$P(0), P(1), \cdots, P(m+1)$ はすべて整数であるとする。ここで、差分多項式 $Q(x)$ を次のように定める。

$$ Q(x) = P(x+1) - P(x) $$

$P(x)$ の最高次項を $c x^{m+1}$ とすると、$P(x+1) - P(x) = c(m+1) x^m + \cdots$ となるため、$Q(x)$ は $m$ 次多項式である。条件より、$P(0), P(1), \cdots, P(m+1)$ はすべて整数であるため、$i = 0, 1, \cdots, m$ に対して、

$$ Q(i) = P(i+1) - P(i) $$

は整数の差であり、すべて整数となる。帰納法の仮定より、$m$ 次多項式 $Q(x)$ はすべての整数 $k$ に対して $Q(k)$ が整数となる。

これを用いて、任意の整数 $k$ に対して $P(k)$ が整数であることを示す。

(i)

$k > 0$ のとき

$$ P(k) - P(0) = \sum_{j=0}^{k-1} \{ P(j+1) - P(j) \} = \sum_{j=0}^{k-1} Q(j) $$

と表せる。$P(0)$ は整数であり、右辺の $Q(j)$ もすべて整数であるから、それらの和である $P(k)$ は整数となる。

(ii)

$k = 0$ のとき条件より $P(0)$ は整数であり、成立する。

(iii)

$k < 0$ のとき $k = -l$ （$l$ は自然数）とおくと、

$$ P(0) - P(-l) = \sum_{j=-l}^{-1} \{ P(j+1) - P(j) \} = \sum_{j=-l}^{-1} Q(j) $$

と表せる。変形すると、

$$ P(-l) = P(0) - \sum_{j=-l}^{-1} Q(j) $$

となる。$P(0)$ は整数であり、$Q(j)$ もすべて整数であるから、$P(-l)$ すなわち $P(k)$ は整数となる。

（i）、（ii）、（iii）より、すべての整数 $k$ に対して $P(k)$ は整数となるため、$n=m+1$ のときも命題は成立する。

以上、（I）、（II）より、数学的帰納法によって題意は証明された。

解法2

実数 $x$ に対して、式 ${}_x \mathrm{C}_{i}$ を次のように定義する。

$$ {}_x \mathrm{C}_{i} = \begin{cases} 1 & (i = 0) \\ \frac{x(x-1)\cdots(x-i+1)}{i!} & (i \ge 1) \end{cases} $$

任意の $n$ 次多項式 $P(x)$ は、定数 $c_0, c_1, \cdots, c_n$ を用いて次のように一意に表すことができる。

$$ P(x) = c_0 {}_x \mathrm{C}_{0} + c_1 {}_x \mathrm{C}_{1} + \cdots + c_n {}_x \mathrm{C}_{n} = \sum_{i=0}^{n} c_i {}_x \mathrm{C}_{i} $$

まず、条件「$P(0), P(1), \cdots, P(n)$ が整数である」ことから、係数 $c_0, c_1, \cdots, c_n$ がすべて整数であることを帰納的に示す。 $P(0) = c_0$ であり、$P(0)$ は整数であるから $c_0$ は整数である。ある整数 $m$ （$0 \le m \le n-1$）について、$c_0, c_1, \cdots, c_m$ がすべて整数であると仮定する。

$$ P(m+1) = \sum_{i=0}^{m+1} c_i {}_{m+1}\mathrm{C}_{i} = \sum_{i=0}^{m} c_i {}_{m+1}\mathrm{C}_{i} + c_{m+1} {}_{m+1}\mathrm{C}_{m+1} $$

ここで、$i \le m+1$ のとき ${}_{m+1}\mathrm{C}_{i}$ は二項係数であるから整数である。また、帰納法の仮定より $c_0, \cdots, c_m$ も整数であるため、$\sum_{i=0}^{m} c_i {}_{m+1}\mathrm{C}_{i}$ は整数となる。さらに ${}_{m+1}\mathrm{C}_{m+1} = 1$ であるから、

$$ c_{m+1} = P(m+1) - \sum_{i=0}^{m} c_i {}_{m+1}\mathrm{C}_{i} $$

と変形できる。仮定より $P(m+1)$ は整数であるため、$c_{m+1}$ は整数の差となり整数である。したがって、帰納的に $c_0, c_1, \cdots, c_n$ はすべて整数であることがわかる。

次に、任意の整数 $k$ に対して $P(k)$ が整数であることを示す。各項の $c_i$ が整数であることは示されたため、任意の整数 $k$ に対して ${}_k \mathrm{C}_{i}$ が整数であることを示せばよい。

(i)

$k \ge 0$ のとき $k \ge i$ のとき、${}_k \mathrm{C}_{i}$ は異なる $k$ 個のものから $i$ 個を選ぶ組み合わせの数であるため、整数となる。 $0 \le k < i$ のとき、${}_k \mathrm{C}_{i}$ の分子に $(k-k)=0$ という因数が含まれるため、${}_k \mathrm{C}_{i} = 0$ となり整数となる。

(ii)

$k < 0$ のとき $k = -l$ （$l$ は自然数）とおくと、

$$ \begin{aligned} {}_k \mathrm{C}_{i} &= \frac{-l(-l-1)\cdots(-l-i+1)}{i!} \\ &= (-1)^i \frac{l(l+1)\cdots(l+i-1)}{i!} \\ &= (-1)^i {}_{l+i-1}\mathrm{C}_{i} \end{aligned} $$

ここで、${}_{l+i-1}\mathrm{C}_{i}$ は自然数 $l+i-1$ から $i$ を選ぶ組み合わせの数であるため整数である。したがって、${}_k \mathrm{C}_{i}$ も整数となる。

（i）、（ii）より、すべての整数 $k$ に対して ${}_k \mathrm{C}_{i}$ は整数である。よって、整数の積と和で表される $P(k)$ は、すべての整数 $k$ に対して整数となることが示された。

解説

「整数値多項式」と呼ばれるテーマの極めて標準的な証明問題である。この性質は、難関大学の整数問題で頻繁に背景知識として問われる。

解法1の差分多項式 $P(x+1) - P(x)$ を用いる手法は、数列の階差をとって次数を下げる操作と同じであり、帰納法と非常に相性が良いである。

解法2の ${}_x \mathrm{C}_{k}$ を基底として多項式を表現する手法は、整数値多項式を扱う上で最も強力な武器となる。一般に、「任意の整数 $x$ で $P(x)$ が整数となる」ことの必要十分条件は、「$P(x)$ が ${}_x \mathrm{C}_{k}$ の整数係数の線形結合で表せること」である。この事実を知っていると、見通しよく解答を組み立てることができる。