# Euler's phi function

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Euler's phi function determines the number of integers less than a given positive integer that are relatively prime to that integer.

### Formulas

Given the prime factorization of $n = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n}$, then one formula for $\phi(n)$ is: $\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_n})$

### Identities

For prime $p$, $\phi(p)=p-1$, because all numbers less than $p$ are relatively prime to it.

For relatively prime $a, b$, $\phi(a)\phi(b) = \phi(ab)$.

### Other Names

• Totient Function
• Euler's Totient Function