The Euler totient function is monotone with respect to divisibility

Prove that if d divides n, then \varphi(d) divides \varphi(n), where \varphi denotes Euler’s totient function.

First, note that the theorem is trivial for n = 1,0,-1. In the remainder we will assume that n is not one of these.

By the Fundamental Theorem of Arithmetic, every integer n can be expressed as a finite and nonempty product of primes n = p_1^{a_1} \ldots p_k^{a_k} in a unique way (up to order). We will call the number k of distinct prime factors of n the length of n.

Let n and d be integers such that d|n. We wish to show that \varphi(d)|\varphi(n); we will proceed by induction on the length of n.

For the base case, note that if n has length 1 then n = p^t for some nonnegative integer t. Moreover, since d|n we have d = p^s for some nonnegative integer s with s \leq t. Then \varphi(n) = p^{t-1}(p-1) = p^{t-s} p^{s-1}(p-1) = p^{t-s} \varphi(d), so that \varphi(d)|\varphi(n).

Suppose now that the proposition is true for all integers of length \ell, and let n be an integer of length \ell + 1. Then we may factor n as n = p^t m where p is a prime not dividing m and m has length \ell. Now if d|n, we may factor d as d = p^s m^\prime for some s \leq t and m^\prime dividing m. Since m has length \ell, we have \varphi(m) = h \varphi(m^\prime) for some h. Thus

\varphi(n)  =  \varphi(p^t) \varphi(m)
 =  p^{t-1}(p-1) h \varphi(m^\prime)
 =  p^{t-s} h \varphi(d),

so that \varphi(d)|\varphi(n). By induction, for all integers n we have that if d|n then \varphi(d)|\varphi(n). \blacksquare

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: