Euler, phi and division

  • Thread starter xax
  • Start date
xax
26
0

Main Question or Discussion Point

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

Answers and Replies

39
0
Have you already proved the totient function is multiplicative?
 
xax
26
0
yes, rodigee
 
39
0
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
26
0
Yes rodigee, this is the way I've solved it, thanks.
 
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?
 
Last edited:
22
0
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 :)
 
2
0
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
 
695
2
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.
 
1
0
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.
 
21,992
3,274
This thread is 4 years old...
 

Related Threads for: Euler, phi and division

  • Last Post
Replies
5
Views
11K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
5K
Replies
4
Views
8K
  • Last Post
Replies
7
Views
5K
Replies
7
Views
9K
Replies
13
Views
15K
Top