COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

場合の数の基本性質

場合の数の基本性質

問題≪オイラーの関数≫

 正の整数 $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{align*} \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{align*} が成り立つ.

背景

  • $\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)\] である.