## The Euler totient function is monotone with respect to divisibility

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 .

### Like this:

Like Loading...

*Related*

or leave a trackback:

Trackback URL.