Maths Olympiad Prep

Library / /833 of 1394

, 2016

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:
Find the number of ordered pairs of integers (a,b)(a, b) such that a,ba, b are divisors of 720720 but abab is not.

Solution

Solution:
First consider the case a,b>0a, b > 0. We have 720=24325720 = 2^4 \cdot 3^2 \cdot 5, so the number of divisors of 720720 is 5×3×2=305 \times 3 \times 2 = 30. We consider the number of ways to select an ordered pair (a,b)(a, b) such that a,b,aba, b, ab all divide 720720. Using the balls and urns method on each of the prime factors, we find the number of ways to distribute the factors of 22 across aa and bb is (62)\binom{6}{2}, the factors of 33 is (42)\binom{4}{2}, the factors of 55 is (32)\binom{3}{2}. So the total number of ways to select (a,b)(a, b) with a,b,aba, b, ab all dividing 720720 is 15×6×3=27015 \times 6 \times 3 = 270. The number of ways to select any (a,b)(a, b) with aa and bb dividing 720720 is 30×30=90030 \times 30 = 900, so there are 900270=630900 - 270 = 630 ways to select aa and bb such that a,ba, b divide 720720 but abab doesn't.

Now, each a,b>0a, b > 0 corresponds to four solutions (±a,±b\pm a, \pm b) giving the final answer of 25202520. (Note that ab0ab \neq 0.)

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.