Prove that if and only if and share exactly the same prime divisors.
Moderator approved CB
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 .
since are distinct , we must have and . and are less than but in this case they are positive integers , this leads to a contradiction .
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 .