Kvant Math Problem 741

Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m44s
Source on kvant.digital

Problem

1. Find at least one natural number that is divisible by 30 and has exactly 30 distinct divisors (including 1 and the number itself).
2. List all such numbers.

M. Lövin

Exploration

Let

$$n=\prod p_i^{a_i}$$

be the prime factorization of a natural number. The number of positive divisors of $n$ is

$$\tau(n)=\prod (a_i+1).$$

We seek numbers divisible by $30=2\cdot3\cdot5$ and satisfying

$$\tau(n)=30.$$

Since

$$30=30=15\cdot2=10\cdot3=6\cdot5=5\cdot3\cdot2,$$

the possible exponent patterns are

$$(29),\quad (14,1),\quad (9,2),\quad (5,4),\quad (4,2,1).$$

Because $n$ is divisible by $30$, at least the primes $2,3,5$ must occur. Hence there must be at least three positive exponents. This immediately eliminates the first four patterns, which contain only one or two positive exponents.

The remaining pattern is $(4,2,1)$. It indeed gives

$$(4+1)(2+1)(1+1)=30.$$

Now every number with exactly $30$ divisors and divisible by $30$ must have exactly three prime factors, with exponents $4,2,1$ in some order. Since $2,3,5$ must all divide the number, the only possible primes are precisely $2,3,5$.

The delicate point is excluding the possibility of a fourth prime factor. If a fourth prime factor were present, there would be at least four positive exponents, and every factor $(a_i+1)$ would be at least $2$, so

$$\tau(n)\ge 2^4=16.$$

But among the factorizations of $30$, none corresponds to four positive exponents. Thus no such case can occur.

The candidate numbers are therefore all assignments of exponents $4,2,1$ to the primes $2,3,5$:

$$2^4 3^2 5,\quad 2^4 3 5^2,\quad 2^2 3^4 5,\quad 2 3^4 5^2,\quad 2^2 3 5^4,\quad 2 3^2 5^4.$$

Problem Understanding

We must determine all natural numbers that are divisible by $30$ and have exactly $30$ positive divisors.

This is a Type A problem, a classification problem. We must prove that every listed number satisfies the conditions and that no other number does.

The core difficulty is translating the condition on the number of divisors into restrictions on the prime factorization and then showing that divisibility by $30$ forces a unique exponent pattern.

The answer should consist of the six numbers obtained by assigning the exponents $4,2,1$ to the primes $2,3,5$.

Proof Architecture

Lemma 1. If $n=\prod p_i^{a_i}$, then $\tau(n)=\prod (a_i+1)$; this is the standard divisor-counting formula.

Lemma 2. If $\tau(n)=30$, then the multiset of positive exponents in the prime factorization of $n$ is one of $(29)$, $(14,1)$, $(9,2)$, $(5,4)$, $(4,2,1)$; this follows from the factorizations of $30$ into integers greater than $1$.

Lemma 3. Since $30\mid n$, the number $n$ has at least three distinct prime divisors, namely $2,3,5$; hence only exponent patterns containing at least three positive exponents can occur.

Lemma 4. The only pattern from Lemma 2 with at least three positive exponents is $(4,2,1)$.

Lemma 5. Any number divisible by $30$ and having exponent pattern $(4,2,1)$ must be one of the six assignments of these exponents to $2,3,5$.

The hardest direction is proving completeness, namely that no other exponent pattern can occur.

Solution

Let

$$n=\prod p_i^{a_i}$$

be the prime factorization of $n$, where all $a_i\ge1$.

The number of positive divisors of $n$ equals

$$\tau(n)=\prod (a_i+1).$$

We are given that

$$\tau(n)=30.$$

Since

$$30=30=15\cdot2=10\cdot3=6\cdot5=5\cdot3\cdot2,$$

the possible multisets of values $(a_i+1)$ are

$$(30),\quad (15,2),\quad (10,3),\quad (6,5),\quad (5,3,2).$$

Subtracting $1$ from each entry gives the possible exponent patterns

$$(29),\quad (14,1),\quad (9,2),\quad (5,4),\quad (4,2,1).$$

Now $30\mid n$. Hence $2$, $3$, and $5$ all divide $n$. Therefore $n$ has at least three distinct prime divisors.

The patterns

$$(29),\ (14,1),\ (9,2),\ (5,4)$$

contain only one or two positive exponents, so they correspond to numbers having only one or two distinct prime divisors. None of them is possible.

Thus the only remaining exponent pattern is

$$(4,2,1).$$

Consequently,

$$n=p^4q^2r,$$

where $p,q,r$ are distinct primes.

Since $2$, $3$, and $5$ divide $n$, the primes $p,q,r$ must be exactly $2,3,5$. Hence every such number is obtained by assigning the exponents $4,2,1$ to the primes $2,3,5$.

This yields precisely the six numbers

$$2^4\cdot3^2\cdot5=720,$$

$$2^4\cdot3\cdot5^2=1200,$$

$$2^2\cdot3^4\cdot5=1620,$$

$$2\cdot3^4\cdot5^2=4050,$$

$$2^2\cdot3\cdot5^4=7500,$$

$$2\cdot3^2\cdot5^4=11250.$$

For each of them,

$$\tau(n)=(4+1)(2+1)(1+1)=5\cdot3\cdot2=30,$$

and each is divisible by $30$.

Hence these six numbers satisfy the required conditions, and every number satisfying the conditions is among them.

Therefore all such numbers are

$$\boxed{{720,\ 1200,\ 1620,\ 4050,\ 7500,\ 11250}}.$$

Verification of Key Steps

The first delicate step is the passage from $\tau(n)=30$ to the exponent patterns. Since

$$\tau(n)=\prod(a_i+1),$$

every factor $a_i+1$ is an integer greater than $1$. The complete factorizations of $30$ into such integers are

$$30,\quad 15\cdot2,\quad 10\cdot3,\quad 6\cdot5,\quad 5\cdot3\cdot2.$$

There is no factorization of $30$ into four or more integers greater than $1$, because the smallest product of four such integers is

$$2^4=16,$$

and the only way to continue multiplying by integers at least $2$ overshoots $30$.

The second delicate step is excluding all patterns except $(4,2,1)$. Since $30\mid n$, the primes $2,3,5$ all occur in the factorization of $n$. Thus at least three exponents are positive. The patterns $(29)$, $(14,1)$, $(9,2)$, and $(5,4)$ contain only one or two positive exponents, so they cannot occur.

The third delicate step is showing that no additional prime factor can appear. The pattern $(4,2,1)$ contains exactly three positive exponents. Therefore $n$ has exactly three distinct prime divisors. Because $2$, $3$, and $5$ already divide $n$, these three primes must be precisely $2$, $3$, and $5$.

Alternative Approaches

One may begin directly from the requirement that $30\mid n$. Writing

$$n=2^a3^b5^c m,$$

where $(m,30)=1$, we obtain

$$\tau(n)=(a+1)(b+1)(c+1)\tau(m)=30.$$

Since $a,b,c\ge1$, each of the first three factors is at least $2$. The product $30=2\cdot3\cdot5$ contains only three prime factors counting multiplicity, which forces

$$\tau(m)=1$$

and hence $m=1$. Then $(a+1,b+1,c+1)$ must be a permutation of $(5,3,2)$, giving the same six numbers.

The main approach is preferable because it classifies all exponent patterns for numbers with $30$ divisors first and then uses the divisibility-by-$30$ condition to eliminate all but one pattern. This makes the completeness of the classification completely transparent.