For use the definition of the Euler phi functionEuler phi

Chapter 9, Problem 40E

(choose chapter or problem)

Problem 40E

For use the definition of the Euler phi function

Euler phi function

For each integer n ≥ 1, φ(n) is the number of positive integers less than or equal to n that have no common factors with n except ±1. For example, φ(10) = 4 because there are four positive integers less than or equal to 10 that have no common factors with 10 except ±1; namely, 1, 3, 7, and 9.

Use the inclusion/exclusion principle to prove the following: If n = pq, where p and q are distinct prime numbers, then φ(n) = (p – 1)(q – 1).