京都大学 1997年度 前期日程 第2次学力試験理系数学 第2問

求める最大公約数を$D$とする。すべての${}_n{\mathrm{C}}_k$の中に $${}_n{\mathrm{C}}_1=n=pq$$ が含まれるので、$D$は$pq$の約数である。したがって、$D$が$p$でも$q$でも割り切れないことを示せば、$D=1$が従う。

まず$p$について調べる。 $${}_{pq}{\mathrm{C}}_p={\displaystyle \frac{pq(pq-1)(pq-2)\cdots (pq-p+1)}{p!}}$$ である。分子に現れる$p$個の整数 $pq,pq-1,pq-2,\dots ,pq-p+1$ のうち、$p$で割り切れるものは$pq$だけである。分母$p!$にも$p$はちょうど1回だけ含まれる。したがって、分子と分母に含まれる$p$の因子はちょうど打ち消し合い、${}_{pq}{\mathrm{C}}_p$は$p$で割り切れない。

よって、すべての二項係数の公約数である$D$も$p$では割り切れない。

同様に $${}_{pq}{\mathrm{C}}_q={\displaystyle \frac{pq(pq-1)(pq-2)\cdots (pq-q+1)}{q!}}$$ を考えると、分子の$q$個の連続因子の中で$q$の倍数は$pq$だけであり、分母$q!$に含まれる$q$とちょうど打ち消し合う。したがって${}_{pq}{\mathrm{C}}_q$は$q$で割り切れない。ゆえに$D$も$q$で割り切れない。 $D$は$pq$の約数であり、しかも$p$でも$q$でも割り切れない。したがって $D=1$ である。

解法1の素因数の個数の議論を合同式に置き換える。${}_{pq}{\mathrm{C}}_p$ を $q$ と $p-1$ 個の比の積に分け、各因子を $p$ を法として簡約する。結果が0でないことから最大公約数に $p$ が入らないと示し、$p,q$ を交換して $q$ も排除する。

最大公約数を $D$ とする。$${}_{pq}{\mathrm{C}}_1=pq$$だから $D\mid pq$ である。

$p$ を法として ${}_{pq}{\mathrm{C}}_p$ を調べる。$${}_{pq}{\mathrm{C}}_p=q\cdot {\displaystyle \frac{(pq-1)(pq-2)\cdots (pq-p+1)}{(p-1)!}}\mathrm{.}$$$1,\dots ,p-1$ はすべて $p$ を法として逆数を持ち、$$pq-i\equiv -i(\mathrm{m}\mathrm{o}\mathrm{d}p)\mathrm{.}$$従って$${}_{pq}{\mathrm{C}}_p\equiv q(-1{)}^{p-1}\equiv ̸0(\mathrm{m}\mathrm{o}\mathrm{d}p)\mathrm{.}$$最後の不等号は $p\mathrm{\ne }q$ がともに素数であることによる。よって ${}_{pq}{\mathrm{C}}_p$ は $p$ で割り切れず、すべての二項係数の公約数 $D$ も $p$ では割り切れない。

同様に $p,q$ を交換すると$${}_{pq}{\mathrm{C}}_q\equiv p(-1{)}^{q-1}\equiv ̸0(\mathrm{m}\mathrm{o}\mathrm{d}q)$$だから、$D$ は $q$ でも割り切れない。

$D$ は $pq$ の約数であり、その素因数 $p,q$ のどちらも持たない。従って$$D=1.$$