Examples

Ο•(1)=1(1)Ο•(2)=1(1)Ο•(3)=2(1,2)Ο•(4)=2(1,3)Ο•(5)=4(1,2,3,4)Ο•(6)=2(1,5)

Properties

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

  • if p is a prime then Ο•(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β‰₯1 a positive integer then Ο•(pk)=pkβˆ’pkβˆ’1

Proof: Since the multiples of p that are less than or equal to pk are: p,2p,3p,…,pkβˆ’1p≀pk we can see that in total there are pkβˆ’1 numbers therefore the other pkβˆ’pkβˆ’1 are relative coprime to pk

Example:

Ο•(24)

multiples of 2 less than 24 are 1βˆ—2,2βˆ—2,3βˆ—2,4βˆ—2,5βˆ—2,6βˆ—2,7βˆ—2,8βˆ—2 which are in total 23 elements, therefore the other 24βˆ’23 are relative prime to 24

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

Proof: TODO, read the chinese remainder theorem

Computation

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

n=p1a1β‹…p2a2β‹…...β‹…pkak

Applying the euler function we get:

Ο•(n)=Ο•(p1a1)β‹…Ο•(p2a2)β‹…...β‹…Ο•(pkak)=(p1a1βˆ’p1a1βˆ’1)β‹…(p2a2βˆ’p2a2βˆ’1)β‹…...β‹…(pkakβˆ’pkakβˆ’1)=(p1a1βˆ’p1a1p1)β‹…(p2a2βˆ’p2a2p2)β‹…...β‹…(pkakβˆ’pkakpk)=p1a1(1βˆ’1p1)β‹…p2a2(1βˆ’1p2)β‹…...β‹…pkak(1βˆ’1pk)=p1a1β‹…p2a2β‹…...β‹…pkakβ‹…(1βˆ’1p1)β‹…(1βˆ’1p2)β‹…...β‹…(1βˆ’1pk)=nβ‹…(1βˆ’1p1)β‹…(1βˆ’1p2)β‹…...β‹…(1βˆ’1pk)=n∏p|n(1βˆ’1p)

Implementation

Time complexity: O(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