### 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;
}