Challange Problem.

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

Moderator approved CB

Printable View

- Sep 30th 2010, 11:00 PMmeleseEuler's phi-function.
**Challange Problem.**

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

Moderator approved CB - Oct 1st 2010, 12:58 AMsimplependulum
Let $\displaystyle m = \prod_i p_i^{a_i} $ and $\displaystyle n = \prod_i q_i^{b_i} $ ( prime factorization of $\displaystyle m $ and $\displaystyle n $ respectively . )

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

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

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

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

since $\displaystyle p_1 , p_2 ,... , q_1 ,q_2 ,... $ are distinct , we must have $\displaystyle p_1 p_2 ... | (p_1 - 1 )(p_2 - 1 ) ... $ and $\displaystyle q_1 q_2 ... | (q_1 - 1 )(q_2 - 1 ) ... $ . $\displaystyle \prod_i \left( 1 - \frac{1}{p_i} \right) $ and $\displaystyle \prod_i \left( 1 - \frac{1}{q_i} \right) $ are less than $\displaystyle 1 $ but in this case they are positive integers , this leads to a contradiction . - Oct 1st 2010, 05:37 AMmelese
I understand that you set $\displaystyle \frac{\phi(m')}{m'}=\frac{\phi(n')}{n'}$ and then arrived at $\displaystyle 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 $\displaystyle \frac{\phi(m')}{m'}=\frac{\phi(n')}{n'}$. - Oct 4th 2010, 12:08 PMBruno J.
Well, he arrives at $\displaystyle p_1p_2\dots | (p_1-1)(p_2-1)\dots$, which implies $\displaystyle 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! - Oct 5th 2010, 08:29 AMBruno J.
Alright. Let $\displaystyle m,n$ be such that $\displaystyle \frac{\varphi(m)}{m}=\frac{\varphi(n)}{m}$. As simplependulum remarked, we can write this equation as

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

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

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

after which we are left with

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

where $\displaystyle P'=P\backslash Q$ and $\displaystyle Q' = Q\backslash P$ (so that $\displaystyle P' \cap Q' = \emptyset$). Now suppose $\displaystyle P' \neq \emptyset$ and take any $\displaystyle p \in P'$. Since $\displaystyle p \notin Q'$, we must have $\displaystyle p | \displaystyle \prod_{p\in P'}(p-1)$, i.e. $\displaystyle p | p'-1$ for some $\displaystyle p' \in P'$. But if you take the greatest $\displaystyle p \in P'$, this is clearly impossible. Hence $\displaystyle P' = \emptyset$, and similarily $\displaystyle Q' = \emptyset$, hence $\displaystyle P=Q$. - Oct 5th 2010, 10:37 AMBruno J.
What I wrote is perhaps what S.P. had in mind.