問題
\(n\)が相異なる素数\(p, q\)の積\(n = pq\)であるとき、\(n-1\)個の数\(_n\mathbb{C}_k\ (1\leq k\leq 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\leq k\leq n-1)\)の最大公約数は\(1\)となる。
解説
具体的に求められそうなものは$$_{pq}\mathbb{C}_1,\ _{pq}\mathbb{C}_p,\ _{pq}\mathbb{C}_q, _{pq}\mathbb{C}_{pq}$$くらいなので、これを求める。
コメント