About Euler's totient function

  • Thread starter Muzza
  • Start date
  • #1
695
0

Main Question or Discussion Point

Does anyone know how to prove that

[tex]\phi(mn) = \phi(m)\phi(n) \frac{d}{\phi(d)}[/tex]

where [tex]m, n \in \mathbb{N}[/tex] and [tex]d = \gcd({m, n})[/tex], without resorting to considering the prime factorizations of m and n? (It's perfectly doable that way, but not particularly elegant).

It can, supposedly, be done by noting that it holds for coprime m and n (a rather classical result), but I don't see how the rest follows... If m, n and d are as in the previous paragraph, then

[tex]\phi(\frac{mn}{d^2}) = \phi(\frac{m}{d}) \cdot \phi(\frac{n}{d})[/tex]

since m/d and n/d are coprime. At this point, one (at least I) feels like multiplying both sides by [tex]\phi(d^2)[/tex], but it doesn't do us much good since mn/d^2 and d^2 might not be coprime (take m = 4, n = 2). Any ideas?
 

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
i'd suggest just making a study of phi(a/b) where a divides b.
 
  • #3
Let m = f1^a1 * f2^a2 ... fk^ak where each fk is a prime (basically the prime factorizatin of m)

Let n = p1^a1 * p2^a2 ... pk^ak where each pk is a prime. The k or each ak has no connection to the prime factorization of n. I'm just making a general prime factorization of numbers.

Let d equal the GCD of m and n, prime factored into z1^a1 * z2^a2 ... zk^ak.

phi(mn) = [mn (1-1/f1)(1-1/f2)...(1-1/fk)(1-1/p1)(1-1/p2)...(1-1/pk)] / [(1-1/z1)(1-1/z2)...(1-1/zk)]

The denominator is there since the GCD contains all prime factors of m and n that are shared and need to be eliminated. The denominator is equal to phi(d)/d.

Simplifying this we get

phi(mn) = [phi(m)phi(n)] / [phi(d)/d]
= phi(m) phi(n) d / phi(d).


You're welcome.
 

Related Threads on About Euler's totient function

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