オイラーのφ関数¶

オイラーのφ関数 $\varphi(n)$ は、$\{1,\ldots,n\}$ のうち $n$ と互いに素な整数の個数を表します。$n$ の相異なる素因数を $p_1,\ldots,p_k$ とすると、

$$ \varphi(n) =n\prod_{j=1}^k\left(1-\frac1{p_j}\right). $$

この積公式から、素因数分解を使うのが自然な計算方法だと分かります。

型付きの直接的な定義¶

素因数分解には同じ素数が繰り返し現れることがあるため、積を取る前に unique で重複を取り除きます。最終結果は整数ですが、途中の各因子も厳密に扱えるよう、有理数演算を用います。

def φ (n : Integer) : Rational :=
  n * product (map (\p -> 1 - 1 / p) (unique (pF n)))

一つの素因数分解を確認する¶

$36=2^2\,3^2$ なので、相異なる素数 $2$ と $3$ だけが積に現れます。

$$ \varphi(36)=36(1-1/2)(1-1/3)=12. $$

(pF 36, unique (pF 36), φ 36)

$(\{2, 2, 3, 3\}, \{2, 3\}, 12)$

最初の20個の値¶

各 $n$ についてφ関数の値と完全な素因数分解を並べて表示すると、素数や素数の冪における値の変化を比較しやすくなります。

map (\n -> (n, φ n, pF n)) (take 20 nats)

$\{(1, 1, \{\}), (2, 1, \{2\}), (3, 2, \{3\}), (4, 2, \{2, 2\}), (5, 4, \{5\}), (6, 2, \{2, 3\}), (7, 6, \{7\}), (8, 4, \{2, 2, 2\}), (9, 6, \{3, 3\}), (10, 4, \{2, 5\}), (11, 10, \{11\}), (12, 4, \{2, 2, 3\}), (13, 12, \{13\}), (14, 6, \{2, 7\}), (15, 8, \{3, 5\}), (16, 8, \{2, 2, 2, 2\}), (17, 16, \{17\}), (18, 6, \{2, 3, 3\}), (19, 18, \{19\}), (20, 8, \{2, 2, 5\})\}$

約数和に関する恒等式¶

すべての正の整数について、次の恒等式が成り立ちます。

$$ \sum_{d\mid n}\varphi(d)=n. $$

約数であるという条件は通常のフィルターで表現でき、先ほどと同じ例を使ってこの恒等式を検証できます。

def divisorsOf (n : Integer) : [Integer] :=
  filter (\d -> divisor n d) [1..n]

def totientDivisorSum (n : Integer) : Rational :=
  sum (map φ (divisorsOf n))

(divisorsOf 36, totientDivisorSum 36)

$(\{1, 2, 3, 4, 6, 9, 12, 18, 36\}, 36)$

まとめ¶

素因数分解、重複除去、写像、積を直接組み合わせることで、オイラーの積公式を厳密な一行の定義として表せます。約数和の検算からは、同じ関数がより深い数論的恒等式にも現れることが分かります。