Challange Problem.

Prove that if and only if and share exactly the same prime divisors.

Moderator approved CB

Printable View

- October 1st 2010, 12:00 AMmeleseEuler's phi-function.
**Challange Problem.**

Prove that if and only if and share exactly the same prime divisors.

Moderator approved CB - October 1st 2010, 01:58 AMsimplependulum
Let and ( prime factorization of and respectively . )

We know , it is obvious that if and share the same prime divisors , the product should equal as we can find a bijection linking and .

Suppose for , they don't share all the same prime divisors , let , where is the greatest common divisor of them . Now and are relatively prime and not equal to ( if so , the other must also be , then , a contradiction . )

Let and be the prime factorization of and respectively .

Consider ,

since are distinct , we must have and . and are less than but in this case they are positive integers , this leads to a contradiction . - October 1st 2010, 06:37 AMmelese
- October 4th 2010, 01:08 PMBruno J.
- October 5th 2010, 09:29 AMBruno J.
Alright. Let be such that . As simplependulum remarked, we can write this equation as

,

where denote, respectively, the sets of prime divisors of . Now we can divide both members by

,

after which we are left with

,

where and (so that ). Now suppose and take any . Since , we must have , i.e. for some . But if you take the greatest , this is clearly impossible. Hence , and similarily , hence . - October 5th 2010, 11:37 AMBruno J.
What I wrote is perhaps what S.P. had in mind.