## Euler, phi and division

Prove that if d divides n then phi(d) divides phi(n).
Thanks
 PhysOrg.com science news on PhysOrg.com >> New language discovery reveals linguistic insights>> US official: Solar plane to help ground energy use (Update)>> Four microphones, computer algorithm enough to produce 3-D model of simple, convex room
 Have you already proved the totient function is multiplicative?
 yes, rodigee

## Euler, phi and division

Then you're home free!

$$d\left| n$$ means $$n = d*a$$ for some integer a. So, bearing in mind the totient function is multiplicative, what can you now say about $$\varphi (n)$$ ?
 Yes rodigee, this is the way I've solved it, thanks.
 There is a crucial problem with your tactic, namely that the Euler phi function is ONLY multiplicative for co-primes. Consider that 2|8. 8=2*4, but 2 and 4 are not co-prime. Phi(2)=1 and Phi(4)=2. Phi(2)*Phi(4)=2. But Phi(8)=4! Multiplicativity of Phi alone is sufficient to prove the property when n=da, d and a co-prime. But not in general. Anyone have insights on how to do this?
 Couldn't you make use of prime decomposition? Take the prime decomposition of n, and let it's totient function be the product of the totient's of it's primes. Do the same for d, and since d|n, the prime decomposition of d is imbedded in n, so for n=d*a, a is just what's left to complete d so that it equals a ... or something like that :)
 Here's how I did it. Prove that if m | n, then phi(m) | phi(n) Note that from phi(p^a) = (p^(a-1))(p-1) for some prime p, it follows that phi(p^a) | phi(p^b) for a | b. This generalizes to phi(k^a) | phi(k^b) for composite k, since phi is multiplicative. Since m | n, there exists some q in Z such that mq = n. Thus, there exists some c, r in Z such that (m^c)r = n where gcd(m, r) = 1 and c ≥ 1. Hence phi(m) | phi(m^c) and phi(m^c) | phi(m^c)phi(r). We have phi(m^c)phi(r) = phi(mc^r) = phi(n) since gcd(m, r) = 1 and phi multiplicative. Thus phi(m) | phi(n). QED
 Here is an alternative, perhaps more in the spirit of "consider the prime factorization of...". Let P(n) be the set of (distinct) primes in the factorization of n. If S is any set of primes {p1, p2, p3, ...}, let F(S) = (1-1/p1) (1-1/p2) (1-1/p3) ... In this notation, we know that phi(n) = n F(P(n)). Now it is time for a Lemma: If S is a subset of P(n), then n F(S) is an integer. Proof: each factor in F(S) is of the form (1 - 1/p) = (p-1)/p Each distinct prime in S exists (at least once) in the factorization of n, cancelling one denominator in F(S) and leaving n F(S) = k (p1-1) (p2-1) (p3-1) ..., where S = {p1, p2, p3, ...} and the integer k = n/(p1 p2 p3 ...). The result follows. Now for the main dish: if m|n, let n = qm. We know that P(n) = P(qm) = P(q) U P(m). Let D be the set difference P(n) - P(m). We know that D is a subset of P(q). Therefore, phi(n) = n F(P(n)) = qm F(P(m)) F(D) = phi(m) q F(D). Since, by the Lemma, q F(D) is an integer, the conclusion follows.
 I'm making a quick comment Euler's totient function IS multiplicative. Someone said it's only for coprimes but there's a general form where the 2 numbers dont have to be coprime phi(mn) = phi(m)phi(n) * d/phi(d) where d is the GCD of m and n.

 Quote by squelchy451 I'm making a quick comment Euler's totient function IS multiplicative. Someone said it's only for coprimes but there's a general form where the 2 numbers dont have to be coprime phi(mn) = phi(m)phi(n) * d/phi(d) where d is the GCD of m and n.
Learn what mulitplicative means.
 Mentor Blog Entries: 8 This thread is 4 years old...

 Tags totient

 Similar Threads for: Euler, phi and division Thread Forum Replies General Math 6 Academic Guidance 1 Differential Equations 14 Precalculus Mathematics Homework 5 General Math 4