We present a formula for Euler’s function.

Since the number 2345 ends in 5, it must be divisible by 5. Hence . Now note that 469 is divisible by 7, and we have . Since 47 is prime, this is the unique prime factorization of 2345.

Among the natural numbers less than 10 the following are relatively prime to 10:

Since there are 4 such numbers, .

We now state the main proposition of this section, whose proof utilizes the Inclusion-Exclusion Principle.

- Proof
- If is a natural number less than which is relatively prime to , then
none of the primes will divide . For each , define to be the subset of consisting
of the multiples of the prime . Then
Now, we use the Inclusion-Exclusion Principle to compute : \begin{align*} \phi (n) &= |A_1^c \cap A_2^c \cap \cdots \cap A_r^c|\\ &= |(A_1 \cup A_2 \cup \cdots \cup A_r)^c|\\ &= |S| - |A_1 \cup A_2 \cup \cdots \cup A_r|\\ &= |S| - \sum |A_i| + \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| + \cdots + (-1)^r|A_1 \cap A_2 \cap \cdots \cap A_r|\\[7pt] &= n - \sum \frac{n}{p_i} + \sum \frac{n}{p_ip_j} - \sum \frac{n}{p_ip_jp_k} + \cdots + (-1)^r \frac{n}{p_1p_2 \cdots p_r}\\[7pt] &= n\left (1 - \sum \frac{1}{p_i} + \sum \frac{1}{p_ip_j} - \sum \frac{1}{p_ip_jp_k} + \cdots + (-1)^r \frac{1}{p_1p_2 \cdots p_r} \right )\\[7pt] &= n \prod _{i = 1}^r \left (1 - \frac{1}{p_i}\right ) \end{align*}

- Proof
- Let the prime factorizations of and be Since and are relatively prime, the prime factorization of is given by According to the proposition, and It is now clear that .

Since , the proposition gives and since , the proposition gives Finally, since , the corollary gives

The proof of the proposition uses a factorization theorem. We explore this theorem in the next example and problem.

The FPC tells us that there will be terms. Further, we can group these terms according to how many of the variables are present. We have Referring back to the proof of the proposition, suppose had three distinct prime factors, . Then the Inclusion-Exclusion Principle gives If we expand these sums, we obtain Noting that the expression in the brackets has the same form as the expansion of with and , we have