Maths Olympiad Prep

Library / /241 of 860

Number theory Difficulty 5.0 AIME Find the answer

Compute the number of positive integers that divide at least two of the integers in the set {11,22,33,44,55,66,77,88,99,1010}\{1^{1}, 2^{2}, 3^{3}, 4^{4}, 5^{5}, 6^{6}, 7^{7}, 8^{8}, 9^{9}, 10^{10}\}.

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

Solution

For a positive integer nn, let \operatorname{rad} n be the product of the distinct prime factors of nn. Observe that if nmmn \mid m^{m}, all prime factors of nn must divide mm, so \operatorname{rad} n \mid m. Therefore, if nn is such an integer, \operatorname{rad} n must divide at least two of the numbers in {1,2,3,4,5,6,7,8,9,10}\{1,2,3,4,5,6,7,8,9,10\}, implying that rad nn is either 1,2,31,2,3, or 5. These have 1,10,61,10,6, and 5 cases, respectively, for a total of 22.

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.