We present a formula for Euler’s function.

(problem 1a) List all pairs that are relatively prime from among the numbers 12, 14, 15, 25 and 45
(problem 1b) Explain why any two successive natural numbers are relatively prime.
(problem 1c) Explain why any two distinct prime numbers are relatively prime.
(problem 1d) Which natural numbers are relatively prime to themselves?
(problem 2) Find the prime factorizations of 1000, 1111, and 43125.
(problem 3a) Find and .
(problem 3b) Find a formula for any prime .

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

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 :

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 .
(problem 4a) Use the proposition to compute and and then use the corollary to compute .
(problem 4b) Use the proposition to establish a formula for where is any prime and is a positive integer.

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

(problem 5a) Multiply and use this to validate the factorization in the last step of the proof of the proposition in the case that has 4 distinct prime factors.
(problem 5b) Conjecture the factorization formula for
(problem 5c) Conjecture the factorization formula for