Olympiad Maths Prep

Library / /13 of 30

Number theory Difficulty 6.0 AIME, harder Prove it Belarus

Find all pairs of positive integers aa and bb such that
ab=160+90(a,b), ab = 160 + 90(a, b),
where (a,b)(a, b) is the greatest common divisor of aa and bb.

Solution

By condition it follows that one of the numbers is divisible by 55. Moreover, exactly one of the numbers is divisible by 55, otherwise (a,b)(a, b) and 90(a,b)90(a, b) are divisible by 2525, and so 160160 is divisible by 2525, a contradiction. Let without loss of generality a5a \neq 5, b5b \neq 5. Then a=5ca = 5c, (a,b)=(5c,b)=(c,b)(a, b) = (5c, b) = (c, b), and the equation can be rewritten as bc=32+18(c,b)bc = 32+18(c, b). Since bcbc and 18(c,b)18(c, b) are divisible by (c,b)(c, b), it follows that (c,b)(c, b) is a factor of 3232, i.e. (c,b)=1,2,4,8,16,32(c, b) = 1, 2, 4, 8, 16, 32.

If (c,b)4(c, b) \ge 4, then bcbc is divisible by 42=164^2 = 16, so 18(c,b)=(bc32)1618(c, b) = (bc - 32) \neq 16, and, therefore, (c,b)8(c, b) \neq 8. Thus bc64bc \neq 64, i.e. 18(c,b)3218(c, b) \neq 32. Therefore, (c,b)16(c, b) \neq 16. If either (c,b)=16(c, b) = 16 or (c,b)=32(c, b) = 32, then bc=162bc = 16^2, but bc=32+1816bc = 32+18 \cdot 16 or bc=32+1864bc = 32+18 \cdot 64, which are impossible. Hence (c,b)2(c, b) \le 2, i.e. is equal to either 11 or 22.

1) Let (c,b)=1(c, b) = 1. Then bc=50bc = 50, and at least one of the numbers is odd. Since b5b \neq 5, we find that either c=25c = 25 and b=2b = 2 or c=50c = 50 and b=1b = 1. This gives the solutions of the initial equation: (a,b)=(125,2)(a, b) = (125, 2) and (a,b)=(250,1)(a, b) = (250, 1).

2) Now let (c,b)=2(c, b) = 2. Then bc=32+36=68bc = 32+36=68. Set b=2b1b=2b_1, c=2c1c=2c_1, where b1b_1 and c1c_1 are coprime. Then b1c1=17b_1c_1 = 17. Hence either c1=1c_1 = 1 and b1=17b_1 = 17 or c1=17c_1 = 17 and b1=1b_1 = 1. This gives the solutions of the initial equation: (a,b)=(10,34)(a, b) = (10, 34) and (a,b)=(170,2)(a, b) = (170, 2).

Since the initial equation is symmetric with respect to aa and bb, we have four more solutions: (34;10)(34; 10), (2;125)(2; 125), (2;170)(2; 170), (1;250)(1; 250).

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.