京都大学 1997年 理系 第2問 解説

方針・初手

• $n-1$ 個の数の最大公約数を求めるため、扱いやすい具体的な $k$ の値を代入して最大公約数の候補を絞り込みます。
• $k=1$ のとき ${}_{n}\mathrm{C}_{1} = pq$ となるため、求める最大公約数は $pq$ の約数（すなわち $1, p, q, pq$ のいずれか）に限られます。
• 最大公約数が $p$ や $q$ の倍数にならないことを示すために、$k=p$ や $k=q$ のときの ${}_{n}\mathrm{C}_{k}$ の性質（特に $p$ や $q$ で割り切れるかどうか）を調べます。

解法1

$(n-1)$ 個の数 ${}_{n}\mathrm{C}_{k}$ ($1 \leqq k \leqq n-1$) の最大公約数を $d$ とおく。

$k=1$ のとき、

$$ {}_{n}\mathrm{C}_{1} = n = pq $$

であるから、$d$ は $pq$ の約数である。 $p, q$ は素数であるから、$pq$ の正の約数は $1, p, q, pq$ のいずれかである。 したがって、$d$ が $p$ の倍数でも $q$ の倍数でもないことを示せば、$d=1$ となる。

$k=p$ のとき、二項係数の性質より

$$ {}_{n}\mathrm{C}_{p} = {}_{pq}\mathrm{C}_{p} = \frac{pq}{p} {}_{pq-1}\mathrm{C}_{p-1} = q \cdot {}_{pq-1}\mathrm{C}_{p-1} $$

となる。ここで、${}_{pq-1}\mathrm{C}_{p-1}$ は整数であり、

$$ {}_{pq-1}\mathrm{C}_{p-1} = \frac{(pq-1)(pq-2) \cdots (pq-p+1)}{(p-1)(p-2) \cdots 1} $$

と表せる。 この分子の各因数 $pq-j$ ($1 \leqq j \leqq p-1$) について、$pq$ は $p$ の倍数であり、$j$ は $p$ より小さい正の整数なので $p$ の倍数ではない。 よって、各因数 $pq-j$ は $p$ で割り切れないため、分子全体としても $p$ を素因数に持たない。 ゆえに、整数 ${}_{pq-1}\mathrm{C}_{p-1}$ は $p$ で割り切れない。 したがって、${}_{n}\mathrm{C}_{p} = q \cdot {}_{pq-1}\mathrm{C}_{p-1}$ は $q$ の倍数であるが、$p$ の倍数ではない。 $d$ は ${}_{n}\mathrm{C}_{p}$ の約数であるから、$d$ は $p$ の倍数ではない。

同様に、$k=q$ のとき、

$$ {}_{n}\mathrm{C}_{q} = {}_{pq}\mathrm{C}_{q} = \frac{pq}{q} {}_{pq-1}\mathrm{C}_{q-1} = p \cdot {}_{pq-1}\mathrm{C}_{q-1} $$

となる。ここで、${}_{pq-1}\mathrm{C}_{q-1}$ は整数であり、

$$ {}_{pq-1}\mathrm{C}_{q-1} = \frac{(pq-1)(pq-2) \cdots (pq-q+1)}{(q-1)(q-2) \cdots 1} $$

と表せる。 この分子の各因数 $pq-i$ ($1 \leqq i \leqq q-1$) について、$pq$ は $q$ の倍数であり、$i$ は $q$ より小さい正の整数なので $q$ の倍数ではない。 よって、各因数 $pq-i$ は $q$ で割り切れないため、分子全体としても $q$ を素因数に持たない。 ゆえに、整数 ${}_{pq-1}\mathrm{C}_{q-1}$ は $q$ で割り切れない。 したがって、${}_{n}\mathrm{C}_{q} = p \cdot {}_{pq-1}\mathrm{C}_{q-1}$ は $p$ の倍数であるが、$q$ の倍数ではない。 $d$ は ${}_{n}\mathrm{C}_{q}$ の約数であるから、$d$ は $q$ の倍数ではない。

以上より、$d$ は $pq$ の約数であるが、$p$ の倍数でも $q$ の倍数でもないため、$d=1$ である。 したがって、$(n-1)$ 個の数 ${}_{n}\mathrm{C}_{k}$ ($1 \leqq k \leqq n-1$) の最大公約数は $1$ である。

解説

• すべての ${}_{n}\mathrm{C}_{k}$ の最大公約数を正面から求めるのではなく、$k=1, p, q$ という特徴的な値に対する ${}_{n}\mathrm{C}_{k}$ に着目し、最大公約数の候補を論理的に絞り込むアプローチが有効です。
• 最初に $k=1$ を調べることで、最大公約数の候補が $1, p, q, pq$ に絞られます。これが解答の大きな足掛かりになります。
• 二項係数の性質 ${}_{n}\mathrm{C}_{k} = \frac{n}{k} {}_{n-1}\mathrm{C}_{k-1}$ を用いることで、特定の素因数を持つかどうかの判定がしやすくなります。この等式は、階乗を用いた定義式から容易に導出でき、整数問題や確率の問題などで頻繁に活躍する重要な性質です。

答え

題意の通り、$(n-1)$ 個の数 ${}_{n}\mathrm{C}_{k}$ ($1 \leqq k \leqq n-1$) の最大公約数は $1$ であることが示された。