Maths Olympiad Prep

Library / /804 of 1394

, 2022

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:

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}\}.

Solution

Solution:

For a positive integer nn, let radn\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 radnm\operatorname{rad} n \mid m.

Therefore, if nn is such an integer, radn\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 radn\operatorname{rad} n is either 1,2,31,2,3, or 55. These have 1,10,61,10,6, and 55 cases, respectively, for a total of 2222.

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.