Maths Olympiad Prep

Library / /87 of 128

Number theory Difficulty 5.9 AIME, harder Prove it Philippines

Problem:

Let mm and nn be relatively prime positive integers. If m3n5m^{3} n^{5} has 209 positive divisors, then how many positive divisors does m5n3m^{5} n^{3} have?

Solution

Solution:

Let d(N)d(N) denote the number of positive divisors of an integer NN. Suppose that the prime factorizations of mm and nn are (piai)\prod\left(p_{i}^{a_{i}}\right) and (qibi)\prod\left(q_{i}^{b_{i}}\right) respectively. Observe that 209 has four positive divisors: 1,11,19,2091, 11, 19, 209.

If m=1m=1, then n5n^{5} would have 209 divisors. Thus, d(n5)=209d\left(n^{5}\right)=209. However, it is known that d(n5)=(5bi+1)d\left(n^{5}\right)=\prod\left(5 b_{i}+1\right), but the latter implies that the remainder of d(n5)d\left(n^{5}\right) when divided by 5 is 1, a contradiction.

Likewise, if n=1n=1, then it implies that the remainder when d(m3)=209d\left(m^{3}\right)=209 is divided by 3 is 1, also a contradiction.

Thus, m,n>1m, n>1, so d(m),d(n)>1d(m), d(n)>1. As mm and nn are relatively prime, then d(m3n5)=d(m3)d(n5)d\left(m^{3} n^{5}\right)=d\left(m^{3}\right) d\left(n^{5}\right). As the only way to factor 209 as a product of 2 integers greater than 1 is as 111911 \cdot 19, then d(m3)d\left(m^{3}\right) and d(n5)d\left(n^{5}\right) are 11 and 19 in some order.

As the remainder when d(m3)d\left(m^{3}\right) and d(n5)d\left(n^{5}\right) is divided by 3 and 5 respectively is 1, then d(m3)=19=(36+1)d\left(m^{3}\right)=19=(3 \cdot 6+1), and d(n5)=11=(52+1)d\left(n^{5}\right)=11=(5 \cdot 2+1). Thus, mm and nn can be expressed as p6p^{6} and q2q^{2} respectively.

Therefore, d(m5n3)=d(p30q6)=(30+1)(6+1)=217d\left(m^{5} n^{3}\right)=d\left(p^{30} q^{6}\right)=(30+1)(6+1)=217.

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.