京都大学 1997年度
理系数学 第2問

解答

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

まず$p$について調べる。 ${}_{pq}{\mathrm{C}}_p=\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=\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$ である。

別解。合同式で見ることもできる。$p$については ${}_{pq}{\mathrm{C}}_p=q\cdot \frac{(pq-1)(pq-2)\cdots (pq-p+1)}{(p-1)!}$ である。$1,2,\dots ,p-1$は$p$で割り切れないので、$(p-1)!$は$p$を法として割ることができる。また $pq-i\equiv -i(\mathrm{mod}p)(1\leqq i\leqq p-1)$ より $\frac{(pq-1)(pq-2)\cdots (pq-p+1)}{(p-1)!}\equiv (-1{)}^{p-1}(\mathrm{mod}p)$ である。$q$は$p$と異なる素数なので$p$で割り切れず、したがって${}_{pq}{\mathrm{C}}_p$は$p$で割り切れない。$q$についても同じ議論で${}_{pq}{\mathrm{C}}_q$が$q$で割り切れないことが分かり、結論は$D=1$である。