Maths Olympiad Prep

Track / Stage 2 / 229 of 240 #469 of 2444

Problem 469

Number theory Difficulty 2.8 Find the answer CEMC Cayley

How many positive integers n20000n \leq 20000 have the properties that 2n2n has 64 positive divisors including 1 and 2n2n, and 5n5n has 60 positive divisors including 1 and 5n5n?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

Suppose n=2r5sp3a3p4a4pkakn=2^{r}5^{s}p_{3}^{a_{3}}p_{4}^{a_{4}}\cdots p_{k}^{a_{k}}. Since 2n2n has 64 divisors and 5n5n has 60 divisors, (r+2)(s+1)(a3+1)(a4+1)(ak+1)=64(r+2)(s+1)\left(a_{3}+1\right)\left(a_{4}+1\right)\cdots\left(a_{k}+1\right)=64 and (r+1)(s+2)(a3+1)(a4+1)(ak+1)=60(r+1)(s+2)\left(a_{3}+1\right)\left(a_{4}+1\right)\cdots\left(a_{k}+1\right)=60. The common divisor of 64 and 60 is 1, 2, or 4. Case 1: (a3+1)(a4+1)(ak+1)=4\left(a_{3}+1\right)\left(a_{4}+1\right)\cdots\left(a_{k}+1\right)=4. n=2253p3p4n=2^{2}5^{3}p_{3}p_{4} or n=2253p33n=2^{2}5^{3}p_{3}^{3}. Case 2: (a3+1)(a4+1)(ak+1)=2\left(a_{3}+1\right)\left(a_{4}+1\right)\cdots\left(a_{k}+1\right)=2. No values of rr and ss work. Case 3: (a3+1)(a4+1)(ak+1)=1\left(a_{3}+1\right)\left(a_{4}+1\right)\cdots\left(a_{k}+1\right)=1. No values of rr and ss work. Therefore, n=500p3p4n=500p_{3}p_{4} or n=500p33n=500p_{3}^{3}. There are 4 possible values of nn.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.