Browse · MathNet
Print60th Belarusian Mathematical Olympiad
Belarus number theory
Problem
Find all pairs of positive integers and () such that where is the greatest common divisor and is the least common multiple of and .
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 , .
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 , .
Final answer
[(12, 72), (24, 36)]
Techniques
Greatest common divisors (gcd)Least common multiples (lcm)Factorization techniquesTechniques: modulo, size analysis, order analysis, inequalities