Euler's phi-function.

**melese** · September 30th 2010, 11:00 PM

Challange Problem.
Prove that $\displaystyle\frac{\phi(m)}{m}=\frac{\phi(n)}{n}$ if and only if $m$ and $n$ share exactly the same prime divisors.

Moderator approved CB

**simplependulum** · October 1st 2010, 12:58 AM

Let $m = \prod_i p_i^{a_i}$ and $n = \prod_i q_i^{b_i}$ ( prime factorization of $m$ and $n$ respectively . )

We know $\frac{\phi(m)}{m} = \prod_i \left( 1 - \frac{1}{p_i} \right)$ , it is obvious that if $m$ and $n$ share the same prime divisors , the product $\prod_i \left( 1 - \frac{1}{p_i} \right)$ should equal $\prod_i \left( 1 - \frac{1}{q_i} \right)$ as we can find a bijection linking $\{\ p_1 , p_2 ,... \}\$ and $\{\ q_1 , q_2 ,... \}\$ .

Suppose for $\frac{ \phi(m) }{m} = \frac{ \phi(n) }{n}$ , they don't share all the same prime divisors , let $m = m' d ~,~ n=n' d$ , where $d$ is the greatest common divisor of them . Now $m'$ and $n'$ are relatively prime and not equal to $1$ ( if so , the other must also be $1$ , then $m=n=d$ , a contradiction . )

Let $\prod_i \left( 1 - \frac{1}{p_i} \right)$ and $\prod_i \left( 1 - \frac{1}{q_i} \right)$ be the prime factorization of $m'$ and $n'$ respectively .

Consider $q_1 q_2 ... (p_1 - 1 )(p_2 - 1 ) ... = p_1 p_2 ... (q_1 -1 )(q_2 - 1 ) ...$ ,

since $p_1 , p_2 ,... , q_1 ,q_2 ,...$ are distinct , we must have $p_1 p_2 ... | (p_1 - 1 )(p_2 - 1 ) ...$ and $q_1 q_2 ... | (q_1 - 1 )(q_2 - 1 ) ...$ . $\prod_i \left( 1 - \frac{1}{p_i} \right)$ and $\prod_i \left( 1 - \frac{1}{q_i} \right)$ are less than $1$ but in this case they are positive integers , this leads to a contradiction .

**melese** · October 1st 2010, 05:37 AM

Originally Posted by simplependulum

Let $\prod_i \left( 1 - \frac{1}{p_i} \right)$ and $\prod_i \left( 1 - \frac{1}{q_i} \right)$ be the prime factorization of $m'$ and $n'$ respectively .

Consider $q_1 q_2 ... (p_1 - 1 )(p_2 - 1 ) ... = p_1 p_2 ... (q_1 -1 )(q_2 - 1 ) ...$ ,

I understand that you set $\frac{\phi(m')}{m'}=\frac{\phi(n')}{n'}$ and then arrived at $q_1q_2...(p_1-1)(p_2-1)...= p_1p_2...(q_1-1)(q_2-1)$ .
If I understood correctly, then I don't see why it's true that $\frac{\phi(m')}{m'}=\frac{\phi(n')}{n'}$ .

**Bruno J.** · October 4th 2010, 12:08 PM

Originally Posted by melese

I understand that you set $\frac{\phi(m')}{m'}=\frac{\phi(n')}{n'}$ and then arrived at $q_1q_2...(p_1-1)(p_2-1)...= p_1p_2...(q_1-1)(q_2-1)$ .
If I understood correctly, then I don't see why it's true that $\frac{\phi(m')}{m'}=\frac{\phi(n')}{n'}$ .

Well, he arrives at $p_1p_2\dots | (p_1-1)(p_2-1)\dots$ , which implies $p_1p_2\dots \leq (p_1-1)(p_2-1)\dots$ , which is absurd, right?

Edit : as melese remarked in a P.M to me, this is not the issue with S.P. 's proof. I'll let him explain!

**Bruno J.** · October 5th 2010, 08:29 AM

Alright. Let $m,n$ be such that $\frac{\varphi(m)}{m}=\frac{\varphi(n)}{m}$ . As simplependulum remarked, we can write this equation as

$\displaystyle \prod_{p\in P}p \prod_{q\in Q}(q-1) = \prod_{q\in Q}q \prod_{p\in P}(p-1)$ ,

where $P,Q$ denote, respectively, the sets of prime divisors of $m,n$ . Now we can divide both members by

$\displaystyle\prod_{u \in P\cap Q}u(u-1)$ ,

after which we are left with

$\displaystyle \prod_{p\in P'}p \prod_{q\in Q'}(q-1) = \prod_{q\in Q'}q \prod_{p\in P'}(p-1)$ ,

where $P'=P\backslash Q$ and $Q' = Q\backslash P$ (so that $P' \cap Q' = \emptyset$ ). Now suppose $P' \neq \emptyset$ and take any $p \in P'$ . Since $p \notin Q'$ , we must have $p | \displaystyle \prod_{p\in P'}(p-1)$ , i.e. $p | p'-1$ for some $p' \in P'$ . But if you take the greatest $p \in P'$ , this is clearly impossible. Hence $P' = \emptyset$ , and similarily $Q' = \emptyset$ , hence $P=Q$ .

**Bruno J.** · October 5th 2010, 10:37 AM

What I wrote is perhaps what S.P. had in mind.

Thread: Euler's phi-function.

LinkBack

Thread Tools

Display

Euler's phi-function.

Similar Math Help Forum Discussions

Euler Phi function II

Euler Phi-Function

euler phi-function

Euler phi-Function

Again, phi euler function

Search Tags