Examples

Properties

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

• if $p$ is a prime, then $\varphi (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\ge 1$ a positive integer, then $\varphi (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,\dots ,p^{k-1}p\le p^k$, we can see that in total there are $p^{k-1}$ numbers; therefore, the other $p^k-p^{k-1}$ are relatively coprime to $p^k$.

Example:

$\varphi (2^4)$

Multiples of $2$ less than $2^4$ are $1\cdot 2,2\cdot 2,3\cdot 2,4\cdot 2,5\cdot 2,6\cdot 2,7\cdot 2,8\cdot 2$, which are in total $2^3$ elements. Therefore, the other $2^4-2^3$ are relatively prime to $2^4$.

• if $a$ and $b$ are relatively prime, then $\varphi (ab)=\varphi (a)\varphi (b)$

Computation

Given a number $n$, let’s decompose it into prime factors (factorization):

Applying the Euler function we get:

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