オイラーのφ関数 (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
    x = 2
    while x*x <= n:
        if n % x == 0:
            res = res // x * (x-1)
            while n % x == 0:
                n //= x
        x += 1
    if n > 1:
        res = res // n * (n-1)
    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)