HMMT-Feb 2012 guts, Problem 21

Let $N$ be a three-digit integer such that the difference between any two positive integer factors of $N$ is divisible by 3 . Let $d(N)$ denote the number of positive integers which divide $N$. Find the maximum possible value of $N \cdot d(N)$.

Solution: We first note that all the prime factors of $n$ must be 1 modulo 3 (and thus 1 modulo 6). The smallest primes with this property are $7,13,19, \ldots$ Since $7^{4}=2401>1000$, the number can have at most 3 prime factors (including repeats). Since $7 \cdot 13 \cdot 19=1729>1000$, the most factors $N$ can have is 6 . Consider the number $7^{2} \cdot 19=931$, which has 6 factors. For this choice of $N, N \cdot d(N)=5586$. For another $N$ to do better, it must have at least 6 factors, for otherwise, $N \cdot d(N)<1000 \cdot 5=5000$. It is easy to verify that $7^{2} \cdot 19$ is the greatest number with 6 prime factors satisfying our conditions, so the answer must be 5586 . $\fbox{5586}$.

Answer: 5586