Maths Olympiad Prep

Library / /398 of 860

Number theory Difficulty 5.1 AIME, harder Find the answer

How many pairs of integers (a,b)(a, b), with 1ab601 \leq a \leq b \leq 60, have the property that bb is divisible by aa and b+1b+1 is divisible by a+1a+1?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The divisibility condition is equivalent to bab-a being divisible by both aa and a+1a+1, or, equivalently (since these are relatively prime), by a(a+1)a(a+1). Any bb satisfying the condition is automatically a\geq a, so it suffices to count the number of values bab-a \in {1a,2a,,60a}\{1-a, 2-a, \ldots, 60-a\} that are divisible by a(a+1)a(a+1) and sum over all aa. The number of such values will be precisely 60/[a(a+1)]60 /[a(a+1)] whenever this quantity is an integer, which fortunately happens for every a5a \leq 5; we count: a=1a=1 gives 30 values of b;b ; a=2a=2 gives 10 values of b;b ; a=3a=3 gives 5 values of bb; a=4a=4 gives 3 values of bb; a=5a=5 gives 2 values of bb; a=6a=6 gives 2 values (b=6b=6 or 48); any a7a \geq 7 gives only one value, namely b=ab=a, since b>ab>a implies ba+a(a+1)>60b \geq a+a(a+1)>60. Adding these up, we get a total of 106 pairs.

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.