Maths Olympiad Prep

Library / /43 of 129

Number theory Difficulty 4.8 AIME Prove it Slovenia

Find all natural numbers mm and nn, such that the sum of their greatest common divisor and their least common multiple equals 101101.

Solution

Let dd denote the greatest common divisor of mm and nn. Then m=dm1m = d m_1 and n=dn1n = d n_1, where m1m_1 and n1n_1 are coprime. The least common multiple of mm and nn is dm1n1d m_1 n_1. We have
101=d+dm1n1=d(1+m1n1). 101 = d + d m_1 n_1 = d(1 + m_1 n_1).
Since 1+m1n121 + m_1 n_1 \ge 2 and 101101 is prime, we can only have d=1d = 1 and m1n1=100m_1 n_1 = 100. The numbers m=m1m = m_1 and n=n1n = n_1 are coprime. Hence, the one that is divisible by 22 must in fact be divisible by 44. The one that is divisible by 55 is divisible by 2525. All possible solutions are (1,100)(1, 100), (4,25)(4, 25), (25,4)(25, 4) and (100,1)(100, 1).

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.