(1) 素数 $p$ と $1 \le r \le p-1$ なる整数 $r$ に対して、二項係数に関する等式 $r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1}$ が成り立つことを示し、また、${}_pC_r$ が $p$ の倍数であることを示す。 (2) 素数 $p$ に対して $2^p$ を $p$ で割った余りを求める。

1. 問題の内容

(1) 素数 $p$ と $1 \le r \le p-1$ なる整数 $r$ に対して、二項係数に関する等式 $r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1}$ が成り立つことを示し、また、${}_pC_r$ が $p$ の倍数であることを示す。

(2) 素数 $p$ に対して $2^p$ を $p$ で割った余りを求める。

2. 解き方の手順

(1)

まず、${}_nC_k = \frac{n!}{k!(n-k)!}$ であることを利用して、与えられた等式の左辺と右辺を計算する。

左辺：

$r \cdot {}_pC_r = r \cdot \frac{p!}{r!(p-r)!} = r \cdot \frac{p \cdot (p-1)!}{r \cdot (r-1)! (p-r)!} = p \cdot \frac{(p-1)!}{(r-1)!(p-r)!}$

右辺：

$p \cdot {}_{p-1}C_{r-1} = p \cdot \frac{(p-1)!}{(r-1)!((p-1)-(r-1))!} = p \cdot \frac{(p-1)!}{(r-1)!(p-r)!}$

したがって、$r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1}$ が成り立つ。

次に、${}_pC_r = \frac{p}{r} \cdot {}_{p-1}C_{r-1}$ であるから、$r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1}$ を ${}_pC_r = \frac{p}{r} \cdot {}_{p-1}C_{r-1}$ と変形できる。

ここで、${}_pC_r$ は整数であり、$1 \le r \le p-1$ より、$r$ は $p$ と互いに素である。

したがって、${}_pC_r$ が整数であるためには、$p \cdot {}_{p-1}C_{r-1}$ が $r$ で割り切れなければならないが、$p$ と $r$ は互いに素なので、${}_{p-1}C_{r-1}$ が $r$ で割り切れなければならない。

しかし、${}_pC_r = \frac{p!}{r!(p-r)!}$ と表せるので、${}_pC_r$ は整数である。

ここで、$r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1}$ より、${}_pC_r = \frac{p \cdot {}_{p-1}C_{r-1}}{r}$ が得られる。${}_pC_r$ が整数なので、$r$ は $p \cdot {}_{p-1}C_{r-1}$ を割り切る。$r$ は $p$ と互いに素であるから、$r$ は ${}_{p-1}C_{r-1}$ を割り切る。つまり、$r$ は ${}_{p-1}C_{r-1}$ の約数である。

$r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1}$ であるので、${}_pC_r = \frac{p}{r} \cdot {}_{p-1}C_{r-1}$ と変形できる。

${}_pC_r$は整数なので、$p \cdot {}_{p-1}C_{r-1}$は$r$で割り切れる。$p$は素数であり、$1 \le r \le p-1$より、$p$は$r$を割り切らないので、${}_{p-1}C_{r-1}$が$r$で割り切れる。

$r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1}$ より、$p \cdot {}_{p-1}C_{r-1}$ は $r$ の倍数である。

ここで、$p$ は素数なので、$p$ と $r$ は互いに素である。

したがって、${}_pC_r$ は $p$ の倍数である。

(2)

フェルマーの小定理より、素数 $p$ に対して、$2^p \equiv 2 \pmod{p}$ である。

したがって、$2^p$ を $p$ で割った余りは $2$ である。

3. 最終的な答え

(1) $r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1}$ が成り立つことと、${}_pC_r$ が $p$ の倍数であることは上記参照。

(2) $2$