Skip to main content
OlympiadHQ

Browse · MathNet

Print

66th Belarusian Mathematical Olympiad

Belarus number theory

Problem

Find all pairs of positive integers , , satisfying the equality .
Solution
Answer: , .

Let denote the greatest common divisor of and , i.e., , , where . Then the given equality can be presented in the form It follows that , and, since and are coprime, . Similarly, . Hence, because and are coprime. Let , then the equation can be presented in the form Note that , whence ; therefore, , or .

Further, , and (1) can be rewritten as We see that is a divisor (less than 20) of . Hence exactly three cases are possible.

1. , , . Then , but is not a divisor of .

2. . If , , then , but is not a divisor of . If , , we have , but is not a divisor of . Finally, if , , then , which gives , whence , i.e., the pair , is a solution.

3. . If , , then , but does not divide . If , , then does not divide . If , , then does not divide . If , , then , which gives , whence , i.e., the pair , is a solution. Finally, if , , then does not divide .

Thus, the equation has two solutions mentioned above.
Final answer
(756, 1008), (600, 960)

Techniques

Techniques: modulo, size analysis, order analysis, inequalitiesGreatest common divisors (gcd)Polynomial operations