Browse · MathNet
Print58th Ukrainian National Mathematical Olympiad
Ukraine number theory
Problem
Find pairs of positive integers , which satisfy the system of equations: Where and are LCM and GCD of numbers .
Solution
Since , then the first equation of the system can be re-written as which gives us quadratic equation with respect to : Its discriminant, also taking into account the second equation of the system, is Which gives and .
Hence, one of the numbers equals GCD, which means it divides the other number. E.g., let , i.e. , then . Hence, these are the possible cases: Case 1. and . Case 2. and . Case 3. .
Hence, one of the numbers equals GCD, which means it divides the other number. E.g., let , i.e. , then . Hence, these are the possible cases: Case 1. and . Case 2. and . Case 3. .
Final answer
(x, y) ∈ {(1, 2017), (2017, 1), (2, 2016), (2016, 2), (1009, 1009)}
Techniques
Greatest common divisors (gcd)Least common multiples (lcm)Factorization techniques