Maths Olympiad Prep

Library / HMMT February /749 of 1302

HMMT February, 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 rad⁡n\operatorname{rad} n be the product of the distinct prime factors of nn. Observe that if n∣mmn \mid m^{m}, all prime factors of nn must divide mm, so rad⁡n∣m\operatorname{rad} n \mid m.

Therefore, if nn is such an integer, rad⁡n\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⁡n\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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.