場合の数の基本
和の法則・個数定理
問題《オイラーの関数》
正の整数 $n$ について, $n$ と互いに素な $1$ 以上 $n$ 以下の整数の個数を $\varphi (n)$ で表す.
このとき, 相異なる素数 $p,$ $q$ に対して
\[\varphi (pq) = \varphi (p)\varphi (q)\]
が成り立つことを示せ.
解答例
$1$ 以上 $pq$ 以下の整数のうち, $pq$ と互いに素な整数は, $p$ の倍数でも $q$ の倍数でもない整数である.
そこで, $1$ 以上 $pq$ 以下の整数からなる集合を全体集合 $U$ として, $p$ の倍数全体を $A,$ $q$ の倍数全体を $B$ とおく.
このとき, $n(A) = q,$ $n(B) = p,$ $n(A\cap B) = 1,$ $\varphi (p) = p-1,$ $\varphi (q) = q-1$ であるから,
\[\begin{aligned}
\varphi (pq) &= n(\bar A\cap\bar B) = n(\overline{A\cup B}) = n(U)-n(A\cup B) \\
&= n(U)-\{ n(A)+n(B)-n(A\cap B)\} \\
&= pq-(q+p-1) = pq-p-q+1 \\
&= (p-1)(q-1) = \varphi (p)\varphi (q)
\end{aligned}\]
が成り立つ.
参考
- $\varphi (n)$ は「オイラーの (トーシェント) 関数」(Euler's (totient) function)と呼ばれる. 一般に, 互いに素な正の整数 $m,$ $n$ に対して \[\varphi (mn) = \varphi (m)\varphi (n)\] が成り立つ (こちらを参照).
- また, 「オイラーの定理」(Euler's theorem) \[ a^{\varphi (n)} \equiv 1\ (\text{mod}\ n)\] の成り立つことが知られている.
- 本問の結果と「オイラーの定理」は「RSA 暗号系」(RSA encryption) に応用されている (こちらを参照).
積の法則
問題《約数の個数の公式》
正の整数 $n$ が $n = p_1{}^{e_1}p_2{}^{e_2}\cdots p_r{}^{e_r}$ ($p_k$: 相異なる素数, $e_k$: 正の整数) と素因数分解されるとき,
$n$ の正の約数の個数 $d(n)$ を求めよ.
解答例
$1 \leqq k \leqq r$ なる各整数 $k$ に対して $1,$ $p_k,$ $\cdots,$ $p_k{}^{e_k}$ の中から $1$ つを選んで掛け合わせると $n$ の正の約数
\[ p_1{}^{j_1}p_2{}^{j_2}\cdots p_r{}^{j_r} \quad (0 \leqq j_k \leqq e_k)\]
が得られ, 逆に $n$ の正の約数はこの形のものしかないから,
\[ d(n) = (e_1+1)(e_2+1)\cdots (e_r+1)\]
である.
対応の利用
問題《試合数》
- (A)
- $n$ 人がトーナメント戦で優勝者を決めるのに必要な試合数を求めよ.
- (B)
- $n$ 人が総当たりのリーグ戦を行うときの試合数を求めよ.
解答例
- (A)
- トーナメント戦では, $1$ 試合ごとにちょうど $1$ 人の敗者が決まり, 最後に $1$ 度も負けなかった $1$ 人が優勝するから, 必要な試合数は $n-1$ である.
- (B)
- 各選手の試合数は $n-1$ である. のべ $n(n-1)$ 人の選手が出場するが, 各試合で $2$ 人の選手が出場するから, 試合数は全部で $\dfrac{n(n-1)}{2}$ である.