Maths Olympiad Prep

Library / /74 of 128

Number theory Difficulty 5.5 AIME, harder Prove it Philippines

Problem:
Let n=223317n = 2^{23} 3^{17}. How many factors of n2n^{2} are less than nn, but do not divide nn?

Solution

Solution:
Let n=223317n = 2^{23} 3^{17}.

The number of factors of nn is (23+1)(17+1)=24×18=432(23+1)(17+1) = 24 \times 18 = 432.

The number of factors of n2n^2 is (2×23+1)(2×17+1)=47×35=1645(2 \times 23 + 1)(2 \times 17 + 1) = 47 \times 35 = 1645.

The factors of n2n^2 come in pairs (d,n2/d)(d, n^2/d), and exactly one of each pair is less than nn (unless d=nd = n). Since n2n^2 is not a perfect square (because nn is not a perfect square), nn is not a factor of n2n^2 such that n2=n×nn^2 = n \times n with nn integer, but in this case nn is a factor of n2n^2.

But n2n^2 is a perfect square, and nn is a factor of n2n^2, and n2=n×nn^2 = n \times n.

So, the number of factors of n2n^2 less than nn is 164512=822\frac{1645 - 1}{2} = 822.

Now, among these, how many do not divide nn?

The factors of nn are among the factors of n2n^2, and all factors of nn are less than or equal to nn (except nn itself). So, among the 432432 factors of nn, nn itself is counted, and 431431 are less than nn.

Therefore, the number of factors of n2n^2 less than nn that do not divide nn is 822431=391822 - 431 = 391.

Answer: 391391.

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.