Maths Olympiad Prep

Library / /89 of 128

Number theory Difficulty 6.0 AIME, harder Prove it Philippines

Problem:

Let NN be the smallest positive integer such that N/15N / 15 is a perfect square, N/10N / 10 is a perfect cube, and N/6N / 6 is a perfect fifth power. Find the number of positive divisors of N/30N / 30.

Solution

Solution:

NN must be of the form N=2m3n5pN = 2^{m} 3^{n} 5^{p} for some nonnegative integers m,n,pm, n, p.

Since N/15=2m3n15p1N / 15 = 2^{m} 3^{n-1} 5^{p-1} is a perfect square, we have m0mod2m \equiv 0 \bmod 2 and np1mod2n \equiv p \equiv 1 \bmod 2.

Since N/10=2m13n5p1N / 10 = 2^{m-1} 3^{n} 5^{p-1} is a perfect cube, we have n0mod3n \equiv 0 \bmod 3 and mp1mod3m \equiv p \equiv 1 \bmod 3.

Since N/6=2m13n15pN / 6 = 2^{m-1} 3^{n-1} 5^{p} is a perfect fifth power, we have p0mod5p \equiv 0 \bmod 5 and mn1mod5m \equiv n \equiv 1 \bmod 5.

By Chinese remainder theorem, we get m16mod30m \equiv 16 \bmod 30, n21mod30n \equiv 21 \bmod 30 and p25mod30p \equiv 25 \bmod 30.

Since NN is as small as possible, we take m=16m = 16, n=21n = 21, p=25p = 25, so N=216321525N = 2^{16} 3^{21} 5^{25}.

Thus the number of positive divisors of N/30=215320524N / 30 = 2^{15} 3^{20} 5^{24} is 162125=840016 \cdot 21 \cdot 25 = 8400.

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.