[math]1997年京都大学理系前期数学2

問題

$n$が相異なる素数$p,q$の積$n=pq$であるとき、$n-1$個の数${}_n{\mathbb{C}}_k(1\le k\le n-1)$の最大公約数は$1$であることを示せ。

方針

具体的に何個か取り出してみる。

解答

$k=1$のとき${}_n{\mathbb{C}}_k=n=pq$である。したがって、最大公約数は$1,p,q,pq$のいずれかになる。$k=p$の時$${}_n{\mathbb{C}}_k=\frac{pq(pq-1)\cdots (pq-p+1)}{p(p-1)\cdots 1}$$ $$=\frac{q(pq-1)\cdots (pq-p+1)}{(p-1)\cdots 1}$$であるが、分子は連続する$p-1$個の整数の積で、$pq$が$p$の倍数なのでいずれも$p$では割り切れない。よって、$k=p$の時${}_n{\mathbb{C}}_k$は$p$では割り切れない。同様に考えると、$k=q$の時${}_n{\mathbb{C}}_k$は$q$では割り切れない。したがって、${}_n{\mathbb{C}}_k(1\le k\le n-1)$の最大公約数は$1$となる。

解説

具体的に求められそうなものは$${}_{pq}{\mathbb{C}}_1,{}_{pq}{\mathbb{C}}_p,{}_{pq}{\mathbb{C}}_q{,}_{pq}{\mathbb{C}}_{pq}$$くらいなので、これを求める。