Browse · MathNet
Print66th 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.
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