Maths Olympiad Prep

Library / /5 of 8

Number theory Difficulty 5.5 AIME, harder Find the answer Italy

How many pairs of positive integers (m,n)(m, n) are there such that the fraction mn\frac{m}{n} is reduced to lowest terms and strictly less than 1, and such that the product mnmn is equal to 12324251 \cdot 2 \cdot 3 \cdot \ldots \cdot 24 \cdot 25 (that is, to the product of the first 25 positive integers)?

Pick one

Solution

Solution:

The answer is (C)\mathbf{( C )}. If mm is a multiple of a certain prime pp, then it must be divisible by the maximum power of pp dividing 25!25! (where by 25!25! we mean the product of the integers from 1 to 25) so that n=25!mn=\frac{25!}{m} has no factors of pp (otherwise the fraction mn\frac{m}{n} would not be reduced to lowest terms). We must therefore count the divisors mm of 25!25! such that

a. mm contains in its factorization some of the prime factors of 25!25!, each raised to the same power to which it appears in the factorization of 25!25! and

b. m<25!mm<\frac{25!}{m}.

Pairing each divisor dd having property (a) with the divisor 25!d\frac{25!}{d}, since between the two only the smaller one will have property (b) (given our requirements on the prime factors of dd, we cannot have d=25!dd=\frac{25!}{d}), we obtain that the divisors to be counted will be half of those for which only property (a) is required.

In the factorization of 25!25! there appear 9 distinct primes: 2,3,5,7,11,13,17,19,232,3,5,7,11,13,17,19,23. The divisors with property (a) are therefore 292^{9}, and among these 282^{8} have property (b).

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 translated into English from it; metadata (topic, difficulty) added by this project.