Olympiad Maths Prep

Library / /17 of 30

Number theory Difficulty 6.3 National olympiad Prove it Belarus

Find all pairs of positive integers aa and bb (aba \le b) such that
ab=300+7[a,b]+5(a,b), ab = 300 + 7[a, b] + 5(a, b),
where (a,b)(a, b) is the greatest common divisor and [a,b][a, b] is the least common multiple of aa and bb.

Solution

Let [a,b]=x[a, b] = x, and (a,b)=y(a, b) = y. It is known (and easy to prove) that ab=[a,b](a,b)ab = [a, b] \cdot (a, b), so ab=xyab = xy. Then the initial equation can be rewritten in the form
xy=300+7x+5yxy7x5y+35=335x(y7)5(y7)=335(x5)(y7)=567. xy = 300 + 7x + 5y \Leftrightarrow xy - 7x - 5y + 35 = 335 \Leftrightarrow x(y - 7) - 5(y - 7) = 335 \Leftrightarrow (x - 5)(y - 7) = 5 \cdot 67.
Factors on the left-hand side are nonnegative integers, and since x=[a,b](a,b)=yx = [a, b] \ge (a, b) = y, we have (x5)>(y7)(x - 5) > (y - 7). So we have two possibilities.

1) x5=67x - 5 = 67 and y7=5y - 7 = 5. Then x=72x = 72 and y=12y = 12. It means that a=12na = 12n, b=12mb = 12m for some relatively prime n,mn, m, and ab=xy=7212ab = xy = 72 \cdot 12, i.e. 12n12m=721212n \cdot 12m = 72 \cdot 12, thus nm=6nm = 6. Taking into account that aba \le b and so nmn \le m, we obtain n=1,m=6n = 1, m = 6. Therefore a=12,b=126=72a = 12, b = 12 \cdot 6 = 72, or n=2,m=3n = 2, m = 3, so a=122=24a = 12 \cdot 2 = 24, b=123=36b = 12 \cdot 3 = 36.

2) x5=335x - 5 = 335 and y7=1y - 7 = 1. Then x=340x = 340 and y=8y = 8. But it is impossible since [a,b]=x[a, b] = x must be divisible by y=(a,b)y = (a, b), but 3408340 \nmid 8.

Therefore, we have two required pairs (12,72)(12, 72), (24,36)(24, 36).

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.