📂整数論

ねじれ関数

同じく見る

• 解析整数論ではのトーティエント関数

定義 ¹

以下のように定義された$\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}$

■