Find all pairs of positive integers and () such that
where is the greatest common divisor and is the least common multiple of and .
Belarusian Mathematical Olympiad
Solution
Let , and . It is known (and easy to prove) that , so . Then the initial equation can be rewritten in the form
Factors on the left-hand side are nonnegative integers, and since , we have . So we have two possibilities.
1) and . Then and . It means that , for some relatively prime , and , i.e. , thus . Taking into account that and so , we obtain . Therefore , or , so , .
2) and . Then and . But it is impossible since must be divisible by , but .
Therefore, we have two required pairs , .
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.