Olympiad Maths Prep

Library / /33 of 60

Number theory Difficulty 6.0 National olympiad Prove it Ukraine

Find pairs of positive integers x,yx, y, which satisfy the system of equations:
{[x,y]+(x,y)=2018,x+y=2018, \begin{cases} [x, y] + (x, y) = 2018, \\ x + y = 2018, \end{cases}
Where [x,y][x, y] and (x,y)(x, y) are LCM and GCD of numbers x,yx, y.

Solution

Since (x,y)[x,y]=xy(x, y) \cdot [x, y] = xy, then the first equation of the system can be re-written as
xy(x,y)+(x,y)=2018, \frac{xy}{(x, y)} + (x, y) = 2018,
which gives us quadratic equation with respect to (x,y)(x, y):
(x,y)22018(x,y)+xy=0. (x, y)^2 - 2018(x, y) + xy = 0.
Its discriminant, also taking into account the second equation of the system, is
D=201824xy=201824x(2018x)=(2x2018)2. D = 2018^2 - 4xy = 2018^2 - 4x(2018 - x) = (2x - 2018)^2.
Which gives x=2018±(2x2018)2x1=xx = \frac{2018 \pm (2x - 2018)}{2} \Rightarrow x_1 = x and x2=2018x=yx_2 = 2018 - x = y.

Hence, one of the numbers equals GCD, which means it divides the other number. E.g., let xyx \le y, i.e. y=kxy = kx, then (k+1)x=2018(k+1)x = 2018. Hence, these are the possible cases:
Case 1. k+1=2018x=1k+1=2018 \Rightarrow x=1 and y=2017y=2017.
Case 2. k+1=1009x=2k+1=1009 \Rightarrow x=2 and y=2016y=2016.
Case 3. k+1=2x=1009=yk+1=2 \Rightarrow x=1009=y.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.