Definition

Euler's phi function represented as \(\phi(n)\) gives for a number \(n\) the number of coprimes in the range \([1..n]\), in other words the quantity numbers in the range \([1..n]\) whose greatest common divisor with \(n\) is the unity

Examples

\[ \begin{align*} \phi(1) &= 1 \quad (1) \\ \phi(2) &= 1 \quad (1) \\ \phi(3) &= 2 \quad (1, 2) \\ \phi(4) &= 2 \quad (1, 3) \\ \phi(5) &= 4 \quad (1, 2, 3, 4) \\ \phi(6) &= 2 \quad (1, 5) \end{align*} \]

Properties

The following three properties will allow us to calculate it for any number:

  • if \(p\) is a prime then \(\phi(p) = p - 1\)

Proof: obviously since \(p\) is a prime the only divisors that it has are \(1\) and \(p\) but \(gcd(1, p) = 1\) so \(1\) falls under the definition of the euler function, therefore the only divisor valid for the euler function for the case above is \(p\)

  • if \(p\) is a prime and \(k \geq 1\) a positive integer then \(\phi(p^k) = p^k - p^{k-1}\)

Proof: Since the multiples of \(p\) that are less than or equal to \(p^k\) are: \(p, 2p, 3p, ..., p^{k-1}p \leq p^k\) we can see that in total there are \(p^{k-1}\) numbers therefore the other \(p^k - p^{k-1}\) are relative coprime to \(p^k\)

Example:

\[\phi(2^4)\]

multiples of \(2\) less than \(2^4\) are \(1 * 2, 2 * 2, 3 * 2, 4 * 2, 5 * 2, 6 * 2, 7 * 2, 8 * 2\) which are in total \(2^3\) elements, therefore the other \(2^4 - 2^3\) are relative prime to \(2^4\)

  • if \(a\) and \(b\) are relatively prime then \(\phi(ab) = \phi(a)\phi(b)\)

Proof: TODO, read the chinese remainder theorem

Computation

Given a number \(n\) let's decompose it into prime factors (factorization):

\[ n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k} \]

Applying the euler function we get:

\[ \begin{align*} \phi(n) &= \phi(p_1^{a_1}) \cdot \phi(p_2^{a_2}) \cdot ... \cdot \phi(p_k^{a_k}) \\ &= (p_1^{a_1} - p_1^{a_1 - 1}) \cdot (p_2^{a_2} - p_2^{a_2 - 1}) \cdot ... \cdot (p_k^{a_k} - p_k^{a_k - 1}) \\ &= (p_1^{a_1} - \frac{p_1^{a_1}}{p_1}) \cdot (p_2^{a_2} - \frac{p_2^{a_2}}{p_2}) \cdot ... \cdot (p_k^{a_k} - \frac{p_k^{a_k}}{p_k}) \\ &= p_1^{a_1} (1 - \frac{1}{p_1}) \cdot p_2^{a_2} (1 - \frac{1}{p_2}) \cdot ... \cdot p_k^{a_k} (1 - \frac{1}{p_k}) \\ &= p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k} \cdot (1 - \frac{1}{p_1}) \cdot (1 - \frac{1}{p_2}) \cdot ... \cdot (1 - \frac{1}{p_k}) \\ &= n \cdot (1 - \frac{1}{p_1}) \cdot (1 - \frac{1}{p_2}) \cdot ... \cdot (1 - \frac{1}{p_k}) \\ &= n \prod_{p|n}(1 - \frac{1}{p}) \end{align*} \]

Implementation

Time complexity: \(O(\sqrt{n})\) Space: \(O(1)\)

int phi(int n) {
  int result = n;
  for (int i = 2; i * i <= n; i += 1) {
    // if `i` is a divisor of `n`
    if (n % i == 0) {
      // divide it by `i^k` so that it's no longer divisible by `i`
      while (n % i == 0) {
        n /= i;
      }
      // all the multiples of `i` are coprime to n, the number of
      // multiples is equal to `i * k` <= n, therefore `k <= n / i`
      result -= result / i;
    }
  }
  if (n > 1) {
    result -= result / n;
  }
  return result;
}

Problems

10179 - Irreducable Basic Fractions 10299 - Relatives 11327 - Enumerating Rational Numbers