Editing Inclusion–exclusion principle (section)

===Euler's phi function===
{{main|Euler's totient function}}

Euler's totient or phi function, ''φ''(''n'') is an [[arithmetic function]] that counts the number of positive integers less than or equal to ''n'' that are [[relatively prime]] to ''n''. That is, if ''n'' is a [[positive integer]], then φ(''n'') is the number of integers ''k'' in the range 1 ≤ ''k'' ≤ ''n'' which have no common factor with ''n'' other than 1. The principle of inclusion–exclusion is used to obtain a formula for φ(''n''). Let ''S'' be the set {1, ..., ''n''} and define the property ''P<sub>i</sub>'' to be that a number in ''S'' is divisible by the prime number ''p<sub>i</sub>'', for 1 ≤ ''i'' ≤ ''r'', where the [[prime factorization]] of

:<math>n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}.</math>

Then,<ref>{{harvnb|van Lint|Wilson|1992|loc=pg. 73}}</ref>

:<math>\varphi(n) = n - \sum_{i=1}^r \frac{n}{p_i} + \sum_{1 \leqslant i < j \leqslant r} \frac{n}{p_i p_j} - \cdots = n \prod_{i=1}^r \left (1 - \frac{1}{p_i} \right ).</math>