Prove that if divides , then divides , where denotes Euler’s totient function.
First, note that the theorem is trivial for . In the remainder we will assume that is not one of these.
By the Fundamental Theorem of Arithmetic, every integer can be expressed as a finite and nonempty product of primes in a unique way (up to order). We will call the number of distinct prime factors of the length of .
Let and be integers such that . We wish to show that ; we will proceed by induction on the length of .
For the base case, note that if has length 1 then for some nonnegative integer . Moreover, since we have for some nonnegative integer with . Then , so that .
Suppose now that the proposition is true for all integers of length , and let be an integer of length . Then we may factor as where is a prime not dividing and has length . Now if , we may factor as for some and dividing . Since has length , we have for some h. Thus
so that . By induction, for all integers we have that if then .