How many pairs of integers , with , have the property that is divisible by and is divisible by ?
Solution
The divisibility condition is equivalent to being divisible by both and , or, equivalently (since these are relatively prime), by . Any satisfying the condition is automatically , so it suffices to count the number of values that are divisible by and sum over all . The number of such values will be precisely whenever this quantity is an integer, which fortunately happens for every ; we count: gives 30 values of gives 10 values of gives 5 values of ; gives 3 values of ; gives 2 values of ; gives 2 values ( or 48); any gives only one value, namely , since implies . 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.