Maths Olympiad Prep

Library / Philippine Mathematical Olympiad /82 of 114

Philippine Mathematical Olympiad

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=2m3n−15p−1N / 15 = 2^{m} 3^{n-1} 5^{p-1} is a perfect square, we have m≡0 mod 2m \equiv 0 \bmod 2 and n≡p≡1 mod 2n \equiv p \equiv 1 \bmod 2.

Since N/10=2m−13n5p−1N / 10 = 2^{m-1} 3^{n} 5^{p-1} is a perfect cube, we have n≡0 mod 3n \equiv 0 \bmod 3 and m≡p≡1 mod 3m \equiv p \equiv 1 \bmod 3.

Since N/6=2m−13n−15pN / 6 = 2^{m-1} 3^{n-1} 5^{p} is a perfect fifth power, we have p≡0 mod 5p \equiv 0 \bmod 5 and m≡n≡1 mod 5m \equiv n \equiv 1 \bmod 5.

By Chinese remainder theorem, we get m≡16 mod 30m \equiv 16 \bmod 30, n≡21 mod 30n \equiv 21 \bmod 30 and p≡25 mod 30p \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 16⋅21⋅25=840016 \cdot 21 \cdot 25 = 8400.

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.