Kvant Math Problem 57
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m37s
Source on kvant.digital
Problem
- Find the number $k$ that is divisible by 2 and 9 and has exactly 14 divisors (including 1 and $k$).
- Prove that if 14 is replaced by 15, the problem has multiple solutions, and if 14 is replaced by 17, there are no solutions at all.
E. B. Dynkin, S. A. Molchanov, A. L. Rozental, A. K. Tolpygo
Mathematical Problems. 3rd ed. – Moscow: Nauka, 1971.
Exploration
Let
$$k=\prod p_i^{a_i}$$
be the prime factorization of $k$. The number of positive divisors of $k$ is
$$\tau(k)=\prod (a_i+1).$$
Since $k$ is divisible by $2$ and $9$, we must have
$$a_2\ge 1,\qquad a_3\ge 2.$$
For part 1, $\tau(k)=14$. Since
$$14=14=2\cdot 7,$$
the possible exponent patterns are $(13)$ and $(6,1)$.
The pattern $(13)$ gives $k=p^{13}$, which cannot be divisible by both $2$ and $9$. Hence only $(6,1)$ remains.
To obtain divisibility by $2$ and $9$, one exponent must belong to $3$ and be at least $2$. The only possibility is
$$k=2\cdot 3^6$$
or
$$k=2^6\cdot 3.$$
The second is not divisible by $9$. Thus the candidate is
$$k=2\cdot 3^6.$$
For $\tau(k)=15$,
$$15=15=3\cdot 5.$$
The exponent patterns are $(14)$ and $(4,2)$.
The pattern $(14)$ is impossible because a single prime power cannot be divisible by both $2$ and $9$. The pattern $(4,2)$ yields numbers of the form
$$2^2\cdot 3^4,\qquad 2^4\cdot 3^2,$$
and also
$$2^2\cdot 3^4 p^0$$
is not a new factorization. Thus at least two distinct solutions already appear.
For $\tau(k)=17$, since $17$ is prime, the only exponent pattern is $(16)$, namely
$$k=p^{16}.$$
No such number is divisible by both $2$ and $9$.
The potentially dangerous step is the classification of exponent patterns from the divisor-count formula. Every possibility must be exhausted.
Problem Understanding
We seek positive integers divisible by both $2$ and $9$ whose number of positive divisors equals a prescribed value.
This is a Type A problem. We must determine all solutions for divisor count $14$, show that there is more than one solution when $14$ is replaced by $15$, and show that no solution exists when $14$ is replaced by $17$.
The core difficulty is translating the condition on the number of divisors into restrictions on the exponents in the prime factorization and then checking which exponent patterns are compatible with divisibility by $2$ and $9$.
The answer for the first part is
$$k=2\cdot 3^6=1458.$$
The reason is that $14=2\cdot 7$, forcing the exponent pattern $(6,1)$, and the divisibility conditions determine uniquely where those exponents must occur.
Proof Architecture
The first lemma is that if
$$n=\prod p_i^{a_i},$$
then the number of positive divisors of $n$ equals
$$\prod (a_i+1).$$
This follows because each divisor is obtained by choosing independently an exponent between $0$ and $a_i$ for every prime.
The second lemma is that the possible exponent patterns for a given divisor count are obtained from all factorizations of that divisor count into integers greater than $1$.
This is a direct reformulation of the divisor-count formula.
The third lemma is that divisibility by $2$ and $9$ is equivalent to the conditions
$$a_2\ge1,\qquad a_3\ge2.$$
This follows from unique factorization.
The hardest direction is proving uniqueness for divisor count $14$, because every admissible exponent pattern must be checked and excluded except one.
Solution
Let
$$k=\prod p_i^{a_i}$$
be the prime factorization of $k$. The number of positive divisors of $k$ is
$$\tau(k)=\prod (a_i+1).$$
Since $k$ is divisible by $2$ and $9$,
$$a_2\ge1,\qquad a_3\ge2.$$
For the first part, assume
$$\tau(k)=14.$$
Since
$$14=14=2\cdot7,$$
the possible collections of numbers $(a_i+1)$ are either $(14)$ or $(7,2)$. Consequently the exponent patterns are either
$$(13)$$
or
$$(6,1).$$
If the exponent pattern is $(13)$, then
$$k=p^{13}$$
for a prime $p$. Such a number cannot be divisible simultaneously by $2$ and by $9=3^2$, because it contains only one prime factor. Hence this case is impossible.
Thus the exponent pattern must be $(6,1)$. Then
$$k=p^6q,$$
where $p$ and $q$ are distinct primes.
Since $k$ is divisible by $9$, the prime $3$ must occur with exponent at least $2$. The exponent $1$ cannot belong to $3$, so necessarily
$$p=3.$$
Hence
$$k=3^6q.$$
Since $k$ is divisible by $2$, the prime $q$ must be $2$. Therefore
$$k=2\cdot3^6=1458.$$
Checking,
$$\tau(1458)=\tau(2\cdot3^6)=(1+1)(6+1)=2\cdot7=14.$$
Thus the unique solution of the first part is
$$\boxed{k=1458}.$$
Now replace $14$ by $15$.
Since
$$15=15=3\cdot5,$$
the exponent patterns are $(14)$ and $(4,2)$.
The pattern $(14)$ gives a single prime power $p^{14}$ and is impossible for the same reason as above.
For the pattern $(4,2)$ we obtain numbers
$$2^2\cdot3^4$$
and
$$2^4\cdot3^2.$$
Both are divisible by $2$ and by $9$, and
$$\tau(2^2\cdot3^4)=(2+1)(4+1)=15,$$
$$\tau(2^4\cdot3^2)=(4+1)(2+1)=15.$$
These are distinct numbers. Hence when $14$ is replaced by $15$, the problem has more than one solution.
Finally, replace $14$ by $17$.
Since $17$ is prime,
$$\tau(k)=17$$
implies
$$a_1+1=17$$
for a single exponent, so
$$k=p^{16}$$
for some prime $p$.
A prime power contains only one prime factor. Therefore it cannot be divisible simultaneously by $2$ and by $9$. No such $k$ exists.
Hence the first part has the unique solution
$$\boxed{1458},$$
the second part has multiple solutions, and for divisor count $17$ there are no solutions at all.
Verification of Key Steps
The first delicate point is the passage from $\tau(k)=14$ to the exponent patterns. Since
$$\tau(k)=\prod(a_i+1),$$
every factor $(a_i+1)$ is at least $2$. The only decompositions of $14$ into such factors are
$$14,\qquad 7\cdot2.$$
These correspond exactly to exponent patterns $(13)$ and $(6,1)$. No other pattern exists.
The second delicate point is the use of divisibility by $9$ in the pattern $(6,1)$. If the exponent $1$ belonged to the prime $3$, then $3$ would occur only to the first power and $9\nmid k$. Thus the exponent $6$ must belong to $3$, forcing
$$k=3^6q.$$
The condition $2\mid k$ then forces $q=2$.
The third delicate point is the case $\tau(k)=17$. Because $17$ is prime, a product of integers greater than $1$ can equal $17$ only if there is exactly one factor. Hence
$$\tau(k)=17$$
implies
$$k=p^{16}.$$
No overlooked exponent pattern is possible.
Alternative Approaches
A shorter approach is to work entirely with the divisor-count formula and factorization of the numbers $14$, $15$, and $17$. After writing
$$\tau(k)=\prod(a_i+1),$$
one immediately lists all possible exponent patterns arising from each divisor count and checks compatibility with the conditions $2\mid k$ and $3^2\mid k$. This yields the answer in a few lines.
The main approach is preferable because it makes explicit why every exponent pattern has been considered and why the divisibility conditions force the placement of the exponents. That eliminates the only place where a classification argument could miss a case.