📂整数論

トーシェント関数

関連リンク

• 解析的整数論におけるトーシェント関数

定義 ¹

次のように定義される$\phi$をオイラーのトーシェント関数という。

$$ \phi ( m ) := \left| \left\{ a \ | \ 1 \le a \le m \land \gcd (a,m) = 1 \right\} \right| = m \prod_{p \mid m} \left( 1 - {{1} \over {p}} \right) $$

説明

トーシェント^totientは、全体を意味するTot-alのTot-と、商を意味するQuo-tientの-tientが付いてできた単語だと理解して差し支えない。数学、それも整数論以外ではまったく使われないうえに、その整数論でさえパイPhi関数あるいはピーPhi関数と書かれることが多い。

$1$から$10$程度までは直接計算して感覚をつかんでみよう。 $$ \begin{align*} \phi ( 1 ) = & \left| \left\{ 1 \right\} \right| = 1 =1 \\ \phi ( 2 ) = & \left| \left\{ 1 \right\} \right| = 2 {{1} \over {2}} = 1 \\ \phi ( 3 ) = & \left| \left\{ 1 , 2 \right\} \right| = 3 {{2} \over {3}} = 2 \\ \phi ( 4 ) = & \left| \left\{ 1 , 3 \right\} \right| = 4 {{1} \over {2}} = 2 \\ \phi ( 5 ) = & \left| \left\{ 1 , 2 , 3 , 4 \right\} \right| = 5 {{4} \over {5}} = 4 \\ \phi ( 6 ) = & \left| \left\{ 1 , 5 \right\} \right| = 6 {{1} \over {2}} {{2} \over {3}} = 2 \\ \phi ( 7 ) = & \left| \left\{ 1 , 2 , 3 , 4 , 5 , 6 \right\} \right| = 7 {{6} \over {7}} = 6 \\ \phi ( 8 ) = & \left| \left\{ 1 , 3 , 5 , 7 \right\} \right| = 8 {{1} \over {2}} = 4 \\ \phi ( 9 ) = & \left| \left\{ 1 , 2, 4 , 5 , 7, 8, \right\} \right| = 9 {{2} \over {3}} = 6 \\ \phi ( 10 ) = & \left| \left\{ 1 , 3 , 7 , 9 \right\} \right| = 10 {{1} \over {2}} {{4} \over {5}} = 4 \end{align*} $$

一見、なぜこれほど計算が難しく規則もなさそうな関数が必要なのか疑問に思うかもしれない。実のところ、美しい性質を豊富に持っているだけでなく、さまざまな理論を支える土台となることがわかるだろう。

定理

素数$p$に対して、$\phi (p^{k}) = p^{k} - p^{k-1}$

証明

戦略: 素数の冪に対する関数値はカウンティングによって簡単に求められる。

---

$p$が素数なので、任意の$n \in \mathbb{N}$に対して$\gcd (p, np) \ne 1$すなわち $$ p , 2p , \cdots (p^{k-1} - 2 ) p , (p^{k-1} - 1 ) p , p^{k} \notin \left\{ a \ | \ 1 \le a \le p^{k} \land \gcd (a,p^{k}) = 1 \right\} $$ これらはちょうど$p^{k-1}$個存在するので、$\phi (p^{k}) = p^{k} - p^{k-1}$

■