Maths Olympiad Prep

Library / /309 of 860

Number theory Difficulty 5.1 AIME, harder Find the answer

Find the number of ordered pairs of integers (a,b)(a, b) such that a,ba, b are divisors of 720 but aba b is not.

A number or a short expression. Spacing and $ signs are ignored.

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 720 is 532=305 * 3 * 2=30. We consider the number of ways to select an ordered pair (a,b)(a, b) such that a,b,aba, b, a b all divide 720. Using the balls and urns method on each of the prime factors, we find the number of ways to distribute the factors of 2 across aa and bb is (62)\binom{6}{2}, the factors of 3 is (42)\binom{4}{2}, the factors of 5 is (32)\binom{3}{2}. So the total number of ways to select (a,b)(a, b) with a,b,aba, b, a b all dividing 720 is 1563=27015 * 6 * 3=270. The number of ways to select any (a,b)(a, b) with aa and bb dividing 720 is 3030=90030 * 30=900, so there are 900270=630900-270=630 ways to select aa and bb such that a,ba, b divide 720 but aba b doesn't. Now, each a,b>0a, b>0 corresponds to four solutions (±a,±b( \pm a, \pm b ) giving the final answer of 2520. (Note that ab0a b \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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.