Maths Olympiad Prep

Library / /450 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

For any positive integer nn, let τ(n)\tau(n) denote the number of positive divisors of nn. If nn is a positive integer such that τ(n2)τ(n)=3\frac{\tau\left(n^{2}\right)}{\tau(n)}=3, compute τ(n7)τ(n)\frac{\tau\left(n^{7}\right)}{\tau(n)}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let the prime factorization of nn be n=p1e1p2e2pkekn=p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{k}^{e_{k}}. Then, the problem condition is equivalent to i=1k2ei+1ei+1=3\prod_{i=1}^{k} \frac{2 e_{i}+1}{e_{i}+1}=3 Note that since 2x+1x+11.5\frac{2 x+1}{x+1} \geq 1.5 for x1x \geq 1, and 1.53>31.5^{3}>3, we have k2k \leq 2. Also, k=1k=1 implies 2e1+1=3(e1+1)2 e_{1}+1=3\left(e_{1}+1\right), which implies e1e_{1} is negative. Thus, we must have k=2k=2. Then, our equation becomes (2e1+1)(2e2+1)=3(e1+1)(e2+1)\left(2 e_{1}+1\right)\left(2 e_{2}+1\right)=3\left(e_{1}+1\right)\left(e_{2}+1\right) which simplifies to (e11)(e21)=3\left(e_{1}-1\right)\left(e_{2}-1\right)=3. This gives us e1=2e_{1}=2 and e2=4e_{2}=4. Thus, we have n=p2q4n=p^{2} q^{4} for primes pp and qq, so τ(n7)τ(n)=τ(p14q28)τ(p2q4)=152935=29\frac{\tau\left(n^{7}\right)}{\tau(n)}=\frac{\tau\left(p^{14} q^{28}\right)}{\tau\left(p^{2} q^{4}\right)}=\frac{15 \cdot 29}{3 \cdot 5}=29.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.