2018年 学習院大学

今回は整数問題です。互いに素がらみの問題で是非完答したいところです。
では、まず互いに素について復習をしておきましょう。

互いに素
$a$と$b$が互いに素とは$a, b$が公約数をもたないこと

たとえば、$5$と$7$は互いに素ですが、$4$と$6$は公約数として$2$をもつので互いに素ではないですね。また、次の定理も非常に重要ですので確認しておきましょう。

$a$と$b$が互いに素でありかつ$bc$は$a$で割り切れるならば、$c$が$a$で割り切れる。

証明

仮定によって、$a$と$b$は互いに素であるから、$a, b$の最小公倍数は$ab$である。
また、仮定によって$bc$は$a$の倍数ゆえ、$a, b$の公倍数であるから$bc$は$ab$の倍数である。したがって、$\dfrac{bc}{ab}=\dfrac{c}{a}$は整数であり、すなわち$c$は$a$で割り切れる。

互いに素がらみの問題を数題解いてみましょう。定義でも確認したとおり、互いに素は否定的なイメージがあるので、基本的に証明は背理法を用いるとよいでしょう。

定石

互いに素の証明は背理法

例題1

$n$を自然数とする。
$n+1$と$n$が互いに素であることを示せ。

方針

「互いに素であることを示せ」ですからやはり定石にしたがって背理法でいきましょう。

解答を見る

$n+1$と$n$が共通の素因数$p$をもつと仮定する。ともに$p$の倍数なので、差をとっても$p$の倍数になるが、$(n+1)-n=1$であり、$p$の倍数にならず矛盾する。したがって、$n+1$と$n$は互いに素である。

例題2

$p$は素数である。
${}_p C_k (k=1, 2, \cdots, p-1)$はいずれも$p$で割り切れることを証明せよ。

方針

非常によく見る問題です。フェルマーの小定理を勉強するとでてくる問題ですね。示したいことは$p$で割り切れるということは$p$の倍数であるということ。
${}_p C_k=\dfrac{p(p-1)\cdots(p-k+1)}{k(k-1)\cdots2\cdot 1}=p\cdot\dfrac{(p-1)\cdots(p-k+1)}{k(k-1)\cdots2\cdot 1}$であるので、$\cdot\dfrac{(p-1)\cdots(p-k+1)}{k(k-1)\cdots2\cdot 1}$が整数であってくれれば示されます。

解答を見る

では、学習院大学の問題の解説に入ります。