Skip to main content
OlympiadHQ

Browse · MathNet

Print

60th 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 , .
Final answer
[(12, 72), (24, 36)]

Techniques

Greatest common divisors (gcd)Least common multiples (lcm)Factorization techniquesTechniques: modulo, size analysis, order analysis, inequalities