Euler, phi and division

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!

[tex]d\left| n[/tex] means [tex]n = d*a[/tex] for some integer a. So, bearing in mind the totient function is multiplicative, what can you now say about [tex]\varphi (n)[/tex] ?

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 dont have to be coprime

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

where d is the GCD of m and n.

jaebond

Learn what mulitplicative means.

micromass

This thread is 4 years old...