欧拉函数

Euler’s Totient Function.

The general case of Euler’s Totient is $\varphi(n)=n\Pi_{p|n}(1-\frac{1}{p})=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_r})$. This is essentially the Inclusion-Exclusion principle.

Code Implementation: Linear Sieve

To calculate a specific totient of $n$, we could design a trivial $O(n\log n)$ algorithm based on the above formula. However, there exists a sieve algorithm that could calculate totients of number $1$ to $n$ in linear time $O(n)$. Below is the code in C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// the Euler sieve
// bool array: is_prime, int array: prime, phi

void sieve() {
    for (int i = 1; i < N; ++i)	is_prime[i] = 1;
    cnt = 0;
    is_prime[1] = 0;
    phi[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (is_prime[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;     // for a prime p, phi[p] = p - 1
        }
        for (int j = 1; j <= cnt && i * prime[j] <= N; ++j) {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j])
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
	else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

Reference & Explanation: (OI Wiki) Linear Sieve for Euler’s totient function

Euler’s Theorem

Since $\gcd(a,n)=1$, $a$ is invertible modulo $n$. According to Euler’s Theorem, $a^{\varphi(n)}\equiv 1\pmod{n}$. Therefore $a\times a^{\varphi(n)-1}\equiv 1\pmod{n}$. $a^{\varphi(n)-1}$ is a multiplicative inverse of $a$ modulo $n$.

An informal proof. (need the knowledge of $\mathbb{Z}_n^{*}$, multiplicative group of integers modulo $n$).

For $a\in\mathbb{Z}n^{*}$, ${r_1,r_2,…r{\varphi(n)}}=(\mathbb{Z}/n)^{*}={ar_1,ar_2,…ar_{\varphi(n)}}$.

Therefore $r_1r_2…r_{\varphi(n)}\equiv (ar_1)(ar_2)…(ar_{\varphi(n)})$, which reduces to $1\equiv a^{\varphi(n)}$. This cancellation is allowed since all $r_i$ have multiplicative inverses modulo $n$.

Reference & Explanation: (Brilliant Math Wiki) Proof of Euler’s Theorem