Does d dividing n imply phi(d) divides phi(n)?

[xax]

Prove that if d divides n then phi(d) divides phi(n).
Thanks

 

[rodigee]

Have you already proved the totient function is multiplicative?

 

[xax]

yes, rodigee

 

[rodigee]

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) ?

 

[xax]

Yes rodigee, this is the way I've solved it, thanks.

 

[hegelec]

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?

 

[Bingk]

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 :)

 

[hegelec]

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

 

[dodo]

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.

 

[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 don't have to be coprime

phi(mn) = phi(m)phi(n) * d/phi(d)

where d is the GCD of m and n.

 

[jaebond]

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 don't 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.

 

[micromass]

This thread is 4 years old...