Euler's totient function

Euler's totient function φ(n) (read "phi of n") counts the integers from 1 to n that are coprime to n: they share no divisor with n except 1. It answers problems that count irreducible fractions with denominator n, or step sizes k that visit every cell of a cycle of length n, for one n up to about 10^{12} or for all n up to about 10^7. To count coprime numbers in another range, use inclusion–exclusion instead.

Explanation

Write the numbers from 1 to 10 in a row and pick those whose greatest common divisor with 10 is 1. The even numbers share 2 with 10, and 5 and 10 share 5. Four numbers remain: 1, 3, 7 and 9.

Fig. 1. The numbers from 1 to 10 that share no divisor with 10 except 1.

For n = 10^{12} this takes 10^{12} gcd calls, hours at about 10^8 simple steps per second (a rule of thumb from time complexity). We need to count the numbers without looking at each one.

Let's count for a bigger number, 30. Its prime factors are 2, 3 and 5. Any common divisor bigger than 1 has a prime factor, and that prime divides 30. A number shares a divisor with 30 exactly when it is a multiple of 2, 3 or 5, so we can count the numbers that must go and subtract them from 30.

15 numbers are multiples of 2, 10 are multiples of 3 and 6 are multiples of 5. That gives 30 − 15 − 10 − 6 = −1, and a count can't be negative. 6 is a multiple of both 2 and 3, so it was subtracted twice. So were 10, 12, 15, 18, 20 and 24, and 30 was subtracted three times. 22 numbers had to go, but 31 were subtracted.

Fig. 2. Subtracting the multiples of 2, 3 and 5 from 30 takes the red numbers away more than once.

Instead, handle one prime at a time and remove its multiples only from the numbers still counted. In Fig. 2 the numbers stand in 5 rows of 6. The multiples of 2 fill columns 2, 4 and 6, so half of the numbers are removed and 15 are still counted. Among them, column 3 holds the multiples of 3, so a third is removed and 10 are still counted, in columns 1 and 5. In each of these two columns exactly one number of five is a multiple of 5: 25 and 5. A fifth is removed, and 8 are still counted: 1, 7, 11, 13, 17, 19, 23 and 29.

It is exactly one in five because going down a column adds 6, and 6 has no factor 5, so the remainders by 5 come round once in every 5 rows.

Fig. 3. Remainders by 5 in the two white columns. 5 and 25 have remainder 0.

Each prime keeps a fixed fraction of the count: 30 · 1/2 · 2/3 · 4/5 = 8. So φ(30) = 8. In general, multiply n by (1 − 1/p) for each distinct prime p that divides n:

To compute it, run trial division with a count that starts at n. Each new prime p found removes its multiples from the count, a 1/p share of it: the count becomes count − count / p.

Start with all n numbers: all 30 are counted, and 30 is left to factor.

Try the next number: 2 · 2 = 4 is not bigger than 30, and 2 divides 30.

Remove its share: half of the 30 counted numbers are multiples of 2, so the count becomes 30 − 15 = 15.

Divide it out: 30 / 2 = 15 is left to factor. The count doesn't change.

Try the next number: 3 · 3 = 9 is not bigger than 15, and 3 divides 15.

Remove its share: a third of the 15 counted numbers are multiples of 3, so the count becomes 15 − 5 = 10.

Divide it out: 15 / 3 = 5 is left to factor.

Stop at the square root of what is left: 4 · 4 = 16 is bigger than 5.

Keep the leftover: 5 is prime and takes a fifth of the 10 counted numbers, so the count becomes 10 − 2 = 8.

1/9

Fig. 4. Step through with the buttons or the arrow keys. White numbers are still counted; red ones are removed at this step.

Step captions, one per frame:

1. Start with all n numbers: all 30 are counted, and 30 is left to factor.

2. Try the next number: 2 · 2 = 4 is not bigger than 30, and 2 divides 30.

3. Remove its share: half of the 30 counted numbers are multiples of 2, so the count becomes 30 − 15 = 15.

4. Divide it out: 30 / 2 = 15 is left to factor. The count doesn't change.

5. Try the next number: 3 · 3 = 9 is not bigger than 15, and 3 divides 15.

6. Remove its share: a third of the 15 counted numbers are multiples of 3, so the count becomes 15 − 5 = 10.

7. Divide it out: 15 / 3 = 5 is left to factor.

8. Stop at the square root of what is left: 4 · 4 = 16 is bigger than 5.

9. Keep the leftover: 5 is prime and takes a fifth of the 10 counted numbers, so the count becomes 10 − 2 = 8.

The loop runs at most about \sqrt{n} times: about 10^6 for n = 10^{12} instead of 10^{12} gcd calls.

Totients of all numbers up to N

Some problems need φ of every number up to N. A loop shaped like the sieve of Eratosthenes computes them all. Start with the value i in the cell of every number i, and go through i = 2, 3, … in order. If the cell of i still holds i, no smaller prime has touched it, so i is prime. Then each multiple of i, i itself included, has a 1/i share of its value removed.

Fig. 5. Each prime takes its share from every multiple, itself included. The last row is φ(1) to φ(12).

When the loop reaches 6, its cell holds 2, so 6 is skipped. Like the sieve of Eratosthenes, it makes about N / p steps for each prime p, O(N \log \log N) in total.

Euler's theorem

Euler's theorem says that a^{\varphi(m)} \equiv 1 \pmod m (see modular arithmetic) when \gcd(a, m) = 1. For example, φ(10) = 4 and 3^4 = 81 = 8 \cdot 10 + 1. Without the condition it fails: φ(8) = 4, but 2^4 = 16 \equiv 0 \pmod 8. For $a$ coprime to $m$, this gives the modular inverse of $a$, a^{\varphi(m) - 1}, and lets a huge exponent $b$ be replaced by b \bmod \varphi(m) before binary exponentiation.

Implementation

In code, what is left to factor is n, the number tried is d and the count is result, all long long. The division in result -= result / d is exact. To see why, write the count as a product. At the start it is 30 = 2 · 3 · 5. Removing half turns the factor 2 into 1: 15 = 1 · 3 · 5. Removing a third turns the 3 into 2: 10 = 1 · 2 · 5. The 5 is still there, so 10 / 5 is exact. Each step turns one factor p of its own prime into p − 1, so every prime not yet handled still divides the count. A d that is not prime never divides n, because its prime factors were divided out before.

1. Start with all n numbers: result = n.

2. Try the next number: d = 2, 3, 4 and so on.

3. Remove its share: if n % d == 0, result -= result / d.

4. Divide it out: while (n % d == 0) n /= d.

5. Stop at the square root of what is left: when d * d > n.

6. Keep the leftover: if n > 1, it is one more prime: result -= result / n.

The program reads one number n from 1 to 10^{12} and prints φ(n). For the main example the input is:

30

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long result = n;                        // start with all n numbers
    for (long long d = 2; d * d <= n; d++) {     // stop at the square root of what is left
        if (n % d == 0) {
            result -= result / d;                // remove its share
            while (n % d == 0) n /= d;           // divide it out
        }
    }
    if (n > 1) result -= result / n;             // keep the leftover
    cout << result << '\n';
}

The program takes O(\sqrt{n}) time and $O(1)$ memory.

All numbers up to N

The sieve fills a vector<int> phi. The division phi[j] / i is exact for the same reason as in result / d. The program reads N (up to about 10^7), then numbers up to N until the input ends, and prints φ of each.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> phi(N + 1);
    for (int i = 1; i <= N; i++) phi[i] = i;     // start with phi[i] = i
    for (int i = 2; i <= N; i++) {
        if (phi[i] == i) {                        // take the next prime
            for (int j = i; j <= N; j += i) {
                phi[j] -= phi[j] / i;             // remove its share from every multiple
            }
        }
    }

    int n;
    while (cin >> n) {                            // 1 <= n <= N
        cout << phi[n] << '\n';
    }
}

For N = 10^7 it runs in about 0.07 seconds and 40 MB. A sum φ(1) + … + φ(n) needs a running total in long long: for N = 10^7 it reaches about 3 \cdot 10^{13}.

Correctness proof

The invariant is that after the shares of some primes of n are removed, the count equals the number of integers from 1 to n that are multiples of none of those primes. When all distinct primes of n are done, this is φ(n).

The step for the next prime p needs one fact: exactly a 1/p share of the numbers still counted are multiples of p. Let $L$ be the product of the primes already removed (1 at the start). Write the numbers from 1 to n in rows of $L$; n is a multiple of L \cdot p, so the rows split into groups of p. Going down a column adds $L$, and each removed prime divides $L$, so a column is either all removed or all still counted. $L$ has no factor p, so within each group of p rows the remainders by p come round once, and every column still counted holds exactly one multiple of p. Fig. 3 shows this for 30 and p = 5, with L = 6.

Trial division finds each distinct prime of n once, and the totient sieve applies to phi[j] the share of each prime factor of j once, so both programs make exactly these steps.

Common mistakes

• Putting result -= result / d inside the while removes a share for every copy of a repeated prime: 49 gives 36 instead of 42. Remove the share once, before the while.

• Copying the loops of the sieve of Eratosthenes. Starting the inner loop at i * i leaves every prime p with phi[p] = p, and 6 with 3. Stopping the outer loop at i * i <= N skips the primes above \sqrt{N}, so for N = 12, 5 keeps 5 and 11 keeps 11. Run i up to N and j from i.

• Counting 1 when the problem doesn't. φ(1) = 1, but a problem that counts fractions m/n with 0 < m < n wants 0 for n = 1. Check the case n = 1 against the statement.

Similar algorithms

Prime factorization runs the same loop and prints every prime factor; the totient uses each distinct prime once.

Counting divisors also starts from the factorization, but multiplies (exponent + 1) for each prime; φ ignores the exponents.

Inclusion–exclusion handles other ranges: the fractions 1 − 1/p multiply only on the range from 1 to n. On 1 to 10, the numbers coprime to 6 are 1, 5 and 7, but 10 · 1/2 · 2/3 = 10/3 isn't even a whole number.

The linear sieve fills φ for all numbers up to N in $O(N)$.

Practice