Maths Olympiad Prep

Library / /96 of 128

Number theory Difficulty 6.1 National Olympiad Prove it Philippines

Problem:

Compute the sum of all possible distinct values of m+nm+n if mm and nn are positive integers such that
lcm(m,n)+gcd(m,n)=2(m+n)+11 \operatorname{lcm}(m, n)+\operatorname{gcd}(m, n)=2(m+n)+11

Solution

Solution:

Let d=gcd(m,n)d=\operatorname{gcd}(m, n). We consider the following cases:

a. Suppose d=1d=1. Then the equation becomes mn+1=2m+2n+11m n+1=2 m+2 n+11 or (m2)(n2)=14(m-2)(n-2)=14. As mm and nn are coprime in this case, exactly one of them is even. This implies that exactly one of the factors m2m-2 and n2n-2 of 1414 is even. Thus, we have (m2,n2){(14,1),(7,2),(2,7),(1,14)}(m-2, n-2) \in \{(14,1),(7,2),(2,7),(1,14)\} so that (m,n){(16,3),(9,4),(4,9),(3,16)}(m, n) \in \{(16,3),(9,4),(4,9),(3,16)\}. The sum of all possible values of m+nm+n is 19+13=3219+13=32.

b. Suppose d2d \geq 2. As dlcm(m,n)d \mid \operatorname{lcm}(m, n), we see that dd divides 2(m+n)+112(m+n)+11. But dd divides both mm and nn, so d11d \mid 11. This forces d=11d=11. Plugging m=11xm=11 x and n=11yn=11 y into the given equation, where gcd(x,y)=1\operatorname{gcd}(x, y)=1, we have lcm(11x,11y)+gcd(11x,11y)=2(11x+11y)+11\operatorname{lcm}(11 x, 11 y)+\operatorname{gcd}(11 x, 11 y)=2(11 x+11 y)+11, which is equivalent to
11lcm(x,y)+11=2(11x+11y)+11xy=2(x+y)(x2)(y2)=4 11 \operatorname{lcm}(x, y)+11=2(11 x+11 y)+11 \Longrightarrow x y=2(x+y) \Longrightarrow(x-2)(y-2)=4
Exactly one of the factors x2x-2 and y2y-2 of 44 is even. We then get (x2,y2){(4,1),(1,4)}(x-2, y-2) \in \{(4,1),(1,4)\} and (x,y){(6,3),(3,6)}(x, y) \in \{(6,3),(3,6)\}, contradicting gcd(x,y)=1\operatorname{gcd}(x, y)=1.

Hence, the sum of all possible values of m+nm+n satisfying lcm(m,n)+gcd(m,n)=2(m+n)+11\operatorname{lcm}(m, n)+\operatorname{gcd}(m, n)=2(m+n)+11 is 3232.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.