オイラーのφ関数 (Euler’s totient function, phi function)

概要

自然数\(n\)の素因数分解が \(n = p_1^{e_1} p_2^{e_2} ... p_k^{e_k}\) (\(p_1, ..., p_k\) はそれぞれ異なる素数) と表される時、

オイラーのφ関数: \(\displaystyle \varphi(n) = n \prod_i \frac{p_i - 1}{p_i}\)

オイラーの定理・フェルマーの小定理

\(a\) と \(n\) を互いに素な整数とするとき、 \(\displaystyle a^{\varphi(n)} \equiv 1\) (mod \(n\)) が成り立つ。

特に \(n\) が素数の時は \(\varphi(n) = n-1\) から、 \(a^{n-1} \equiv 1\) (mod \(n\)) が成り立つ。 (フェルマーの小定理)

実装

# calculate φ(n)
def euler_phi(n):
  res = n
  for x in range(2, int(n**.5)+1):
    if n % x == 0:
      res = res // x * (x-1)
      while n % x == 0:
        n //= x
  return res

# calculate φ(x) for 1 <= x <= M
M = 10**6
*phi, = range(M+1)
for x in range(2, M+1):
  if phi[x] == x:
    for y in range(x, M+1, x):
      phi[y] = phi[y] // x * (x-1)