次: メビウスの反転公式 上: オイラーの関数 前: オイラーの関数

オイラーの関数$\varphi (n)$

自然数 $1,\ 2,\ \cdots,\ n$のなかにある$n$と互いに素な整数$x$の個数を$\varphi (n)$で表す． 例えば，

$$\begin{eqnarray*} \varphi(1)=1,&&(x=1)\\ \varphi(2)=1,&&(x=1)\\ \varphi(3)=... ... \varphi(5)=4,&&(x=1,\ 2,\ 3,\ 4)\\ \varphi(6)=2,&&(x=1,\ 5) \end{eqnarray*}$$

$\varphi (n)$をオイラーの関数という． $\varphi (n)$は自然数を定義域とする関数である．

$p$ が素数ならば，明らかに

$$\varphi(p)=p-1$$

である．また同じく$p$ が素数ならば

$$\varphi(p^e)=p^e-p^{e-1}=p^e \left(1-\dfrac{1}{p} \right)$$

である．なぜなら1から $p^e$ までの数のなかで $p^e$ と互いに素ではないものは， $p$ で割り切れるものに他ならず，それは

$$1\cdot p,\ 2\cdot p,\ \cdots,\ p^{e-1}\cdot p$$

の $p^{e-1}$ 個だけあるからである．

$n$を法とする合同関係による商集合$\mathbb{Z}_n$は $n$個の要素からなる集合であった．

$$\mathbb{Z}_n=\{\overline{0},\ \overline{1},\ \cdots,\ \overline{n-1}\}$$

である． さて，一つの $\overline{k}$ 内の要素はすべて $n$ と互いに素であるか， すべて $n$ と互いに素でないか，のいずれかであって，一部のみが互いに素 ということはない． なぜなら$\overline{k}$ の要素 $x$ はすべて $x=k+nt\ (t\ 整数)$ と書け，

$$(k+nt,\ n)=(k,\ n)$$

となるからである (この等号の証明はユークリッドの互除法の原理の証明と同じ)．

したがって「剰余類 $\overline{k}$ が $n$ と互いに素である」ということが意味を持つ． $n$ と互いに素な剰余類 $\overline{k}$ を既約類という．またすべての既約類の 代表の一組を既約剰余系という．既約類は$\varphi (n)$個ある．

整数で定義された関数 $F(x)$ が互いに素な二つの整数$a$と$b$に 対して

$$F(ab)=F(a)F(b)$$

が成り立つとき，乗法的関数という．

定理 17
     $\varphi (n)$は乗法的関数である．すなわち $a$ と $b$ が互いに素ならば，

$$\varphi(ab)=\varphi(a)\varphi(b)$$ (2.19)

が成り立つ．■

証明     $a$ を法とする既約類 $\overline{k}_a$ ， $b$ を法とする既約類 $\overline{l}_b$ をとる．

集合

$$A=\{ bx+ay\,\vert\,x \in \overline{k}_a,\ y \in \overline{l}_b\}$$

を考える． これは $ab$ を法とする剰余類を定める． なぜなら，整数 $s,\ t$ を用いて $x=k+as,\ y=l+bt$ と表すと

$$bx+ay=bk+al+ab(s+t)$$

となり，整数 $s,\ t$ の取り方を変えても $ab$ を法として合同だから剰余類 $A=\overline{bk+al}_{ab}$ となる．

さらにこれは既約類である． なぜならもし $bx+ay$ が $ab$ と互いに素でないとする． $a$ と $b$ が互いに素なので $a$ または $b$ と互いに素でない． $a$ と互いに素でないとする．

$$(bx+ay,\ a)\ne 1\ \iff\ (bx,\ a)\ne 1\ \iff\ (x,\ a)\ne 1\ \iff\ (k,\ a)\ne 1$$

となり $\overline{k}_a$が $a$ を法とする既約類であることに反するからである．

ここで $k'\not \equiv k\quad (\bmod.\ a)$ なる $k'$ をとると

$$bk'+al\not \equiv bk+al\quad (\bmod.\ ab)$$

である．なぜならもし $bk'+al \equiv bk+al\quad (\bmod.\ ab)$なら $bk'\equiv bk\quad (\bmod.\ ab)$ であるが $a$ と $b$ が互いに素なので $k'\equiv k\quad (\bmod.\ a)$とならねばならないからである．

つぎに $ab$ を法とする任意の既約類 $\overline{m}_{ab}$ をとる． $a$ と $b$ が互いに素なので $bk+al=m$ となる $k,\ l$ が存在する． ゆえに既約類 $\overline{m}_{ab}$ は既約類 $Z_a(k)$ と既約類 $Z_b(l)$ から上の方法で作られる． したがって $a$ を法とする既約類 $\overline{k}_a$と$b$ を法とする既約類 $\overline{l}_b$の一組と $ab$ を法とする既約類 $\overline{m}_{ab}$は一対一に対応する． この組は $\varphi(a)\varphi(b)$ 個あるので$(\ref{61})$が示された□

これが基本的な事実である．この証明は剰余類の定義にたちかえって行った． なお中国の剰余定理13を用いれば証明は簡明である．すなわち次のようになる．

別証明     いま $\alpha_1,\ \alpha_2,\ \cdots,\ \alpha_m\ ,\ m=\varphi(a)$ および $\beta_1,\ \beta_2,\ \cdots,\ \beta_n\ ,\ n=\varphi(b)$ をそれぞれ $a$ と $b$ を法とする既約剰余系の一組とする． $mn=\varphi(a)\varphi(b)$ 個の組合せの一つ $\alpha_i,\ \beta_j$ に対して

$$\gamma\equiv \alpha_i\ (\bmod.\ a)\ ,\quad \gamma \equiv \beta_j\ (\bmod.\ b)$$ (2.20)

となる $\gamma$ が $ab$ を法として一つずつある． $\gamma$ は $ab$ と互いに素である．

逆に $(\gamma,\ ab)=1$ とすると，(2.20)となる $\alpha_i,\ \beta_j$ が一意に決まる． ゆえに $ab$ を法とする既約代表の一組の各数 $\gamma$ と $\alpha_i,\ \beta_j$ の組の 間に一対一の対応が成り立つ．したがって$(\ref{61})$が示された．□

$\varphi (n)$は次の定理によって計算される．

定理 18
$n$ を素数べきに分解して

$$n=p^{\alpha}q^{\beta}r^{\gamma}\cdots$$

とすると

$$\varphi(n)=n \left(1- \dfrac{1}{p} \right) \left(1- \dfrac{1}{q} \right)\left(1- \dfrac{1}{r} \right)\cdots$$ (2.21)

が成り立つ．■

証明     定理17から

$$\begin{eqnarray*} \varphi(n)&=&\varphi(p^{\alpha}q^{\beta}r^{\gamma}\cdots)\\ ... ...left(1- \dfrac{1}{q} \right)\left(1- \dfrac{1}{r} \right)\cdots \end{eqnarray*}$$

つまり，$(\ref{62})$が示された．□

例 2.2.1        $a=3,\ b=5$ とする．

$$\begin{eqnarray*} \alpha=1,\ 2,\ \beta=1,\ 2,\ 3,\ 4&&\varphi(3)=2,\ \varphi(5)=4\\ \gamma=1,\ 2,\ 4,\ 7,\ 8,\ 11,\ 13,\ 14&&\varphi(15)=8\\ \end{eqnarray*}$$

であるが, $5\alpha+3\beta\quad (\bmod.\ 15)$ と，別証の$\gamma$を計算すると

$$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert c\ve... ...11&14&2&13&1&4&7\\ \gamma&1&7&13&4&11&2&8&14 \end{array}$$

$d\vert n$ は $d$ が $n$ を割り切ることを意味する記号であった． $d=1,\ n$ のときも$d\vert n$である． $$\sum_{d\vert n}$$と書けば，和は $n$ のすべての約数(1も $n$ も含む)にわたるものとする．

定理 19
    

$$\sum_{d\vert n} \varphi(d)=n$$ (2.22)

である．■

証明     $d$ を $n$ の約数として， 1から $n$ までの数 $x$ で， $(x,\ n)=d$ となるものは $\varphi \left(\dfrac{n}{d} \right)$ 個ある．

なぜなら

$$(x,\ n)=d\quad \iff \quad \left(\dfrac{x}{d},\ \dfrac{n}{d} \right)=1$$

であるから， その個数は1から $\dfrac{n}{d}$ までの中にある $\dfrac{n}{d}$ と互いに素な数の 個数に等しい． つまり $\varphi \left(\dfrac{n}{d} \right)$個である．

1から $n$ までの数 $x$ は $(x,\ n)$ の値が等しいものに分類できるので

$$\{\ 1,\ 2,\ \cdots,\ n\ \}=\bigcup_{d\ \vert\ n}\{\ x\ \vert\ (x,\ n)=d,\ 1\le x \le n \ \}$$

である．したがって，$d$ が $n$ の約数全体を動くとき(1と $n$ を含む)．この方法で 1から $n$ までの数はちょうど一度ずつ数えられる．

$$∴\quad \sum_{d\vert n} \varphi \left(\dfrac{n}{d} \right)=n$$

$d$ が $n$ の約数全体を動くとき $\dfrac{n}{d}$ も $n$ の約数全体を動くので， (2.22)が示された． □

例 2.2.2        $n=15$ とする．

$$\begin{array}{c\vert l\vert l} d&\quad \quad x&\ \varphi... ...\ 15&15&1=\varphi(1)\\ \hline &&計\ 15 \end{array}$$

例 2.2.3        $n=12$ とする．

$$\begin{array}{c\vert l\vert l} d&\quad \quad x&\ \varphi... ...\ 12&12&1=\varphi(1)\\ \hline &&計\ 12 \end{array}$$

次: メビウスの反転公式 上: オイラーの関数 前: オイラーの関数