- #1

- 26

- 0

## Main Question or Discussion Point

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

Thanks

Thanks

- Thread starter xax
- Start date

- #1

- 26

- 0

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

Thanks

Thanks

- #2

- 39

- 0

Have you already proved the totient function is multiplicative?

- #3

- 26

- 0

yes, rodigee

- #4

- 39

- 0

[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] ?

- #5

- 26

- 0

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

- #6

- 2

- 0

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?

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?

Last edited:

- #7

- 22

- 0

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

- #8

- 2

- 0

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

- #9

- 695

- 2

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.

- #10

- 25

- 0

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.

- #11

- 1

- 0

Learn what mulitplicative means.

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.

- #12

- 22,097

- 3,277

This thread is 4 years old...

- Last Post

- Replies
- 5

- Views
- 11K

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 5K

- Last Post

- Replies
- 4

- Views
- 8K

- Last Post

- Replies
- 7

- Views
- 5K

- Replies
- 7

- Views
- 9K

- Replies
- 1

- Views
- 3K

- Last Post

- Replies
- 3

- Views
- 2K