2
$\begingroup$

Find the highest natural number which is divisible by $30$ and have exactly $30$ different positive divisors.

What I Tried: I am not sure about any specific approach to this problem. Of course as the number is divisible by $30$ , some of the factors of the number would be $1,2,3,5,6,10,20,30$ , but that only makes $8$ divisors and there will be $12$ more which I have no idea of .

Can anyone help me?

$\endgroup$
2
  • $\begingroup$ Does this help? www2.math.upenn.edu/~deturck/m170/wk2/numdivisors.html $\endgroup$ Dec 27, 2020 at 16:57
  • $\begingroup$ After you have the 8-divisors: 1, 2, 3, 5, 6, 10, 15 (not 20), and 30, you add more by multiplying by 22-more (not 12) "large" prime numbers to obtain your "large natural number". Because there is no limit on the "large" prime numbers, there is no upper limit on the "large natural number" you seek. Someone could always choose a larger prime in substitution for one of the 22. $\endgroup$
    – Jim Clark
    Dec 27, 2020 at 18:47

5 Answers 5

7
$\begingroup$

(I'm assuming you know the number theoretic way to count the number of divisors of an integer $ n = 2^a \times 3^b \times 5^c \ldots $, which is $ \sigma_0 (n) = (a+1)(b+1)(c+1) \ldots$. If not, go read up on it.)

Let $n$ be such a number.

Hint: Since $ 30 = 2 \times 3 \times 5 $, show that $ n = 2^a \times 3^b \times 5^c$.
In particular, conclude that $n$ cannot have any other prime factors.

Note that every distinct prime factor of $n$ contributes at least one prime factor (not necessarily distinct) of $ \sigma_0 (n)$.
Since $30 \mid n$, so $n$ has at least 3 prime factors (2, 3, 5), which contribute at least 3 (not necessarily distinct) prime factors to $ \sigma_0 (n) = 30$. Since this has 3 prime factors, we conclude that $n$ can have no other prime factors.
Hence, $n = 2^a \times 3^b \times 5^c$.

Hence, the largest natural number is $ 5^4 \times 3^2 \times 2^1$.


Generlization: If $N = \prod p_i$ is the product of distinct primes, then the highest natural number which is divisible by $N$ and has exactly $N$ different positive divisors is $\prod p_i ^ { p_i - 1 } $.

$\endgroup$
3
  • $\begingroup$ +1 for clear and elegant clarification $\endgroup$ Dec 27, 2020 at 17:07
  • $\begingroup$ Got it, thanks for the hint. $\endgroup$
    – Anonymous
    Dec 27, 2020 at 17:17
  • 1
    $\begingroup$ @hardmath Alright I'd add my one-line proof, since that seems to be the part that trips people up. $\endgroup$
    – Calvin Lin
    Dec 28, 2020 at 16:45
2
$\begingroup$

If $n$ has $k$ prime divisors then $$\sigma (n) \geq \underbrace{(1+1)(1+1)\cdots (1+1)}_{k\; \rm times} = 2^k$$

So $2^k\leq 30$ and thus $k\leq 4$. So $n$ has $3$ or $4$ prime divisors.

  • If $\color{red}{k=4}$ then $n= 2^a3^b5^cp^d$, where $p$ is prime greater than $5$. Now we have $$(a+1)(b+1)(c+1)(d+1)= 30$$ which is impossible.
  • If $\color{green}{k=3}$ then $n= 2^a3^b5^c$. Now we have $$(a+1)(b+1)(c+1)= 30$$ which is possible if $a=1$, $b=2$ and $c=4$ or any permutation of them.
$\endgroup$
1
  • $\begingroup$ FYI The first part could be further strengthened to conclude directly that $k = 3$, especially for the more general case. See my edited proof. $\endgroup$
    – Calvin Lin
    Dec 28, 2020 at 16:50
1
$\begingroup$

Not a 'real' answer, but it was too big for a comment. I think that you're looking for a solution without using a calculator or PC but maybe this gives some insight. I did only a quick search with the following bound: $1\le\text{n}\le10^8$.

I wrote and ran some Mathematica-code:

In[1]:=Clear["Global`*"];
\[Alpha] = 10^8;
ParallelTable[
  If[TrueQ[Length[Divisors[n]] == 30 && IntegerQ[n/30]], n, 
   Nothing], {n, 1, \[Alpha]}] //. {} -> Nothing

Running the code gives:

Out[1]={720, 1200, 1620, 4050, 7500, 11250}

We can see that for $1\le\text{n}\le10^8$ the number $\text{n}=11250$ is the biggest possible with the desired properties:

In[2]:=11250/30

Out[2]=375

In[3]:=Divisors[11250]

Out[3]={1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 125, 150, 225, 
250, 375, 450, 625, 750, 1125, 1250, 1875, 2250, 3750, 5625, 11250}
$\endgroup$
0
$\begingroup$

30=2x3x5 So the exponents of 2,3, and 5 have to be 2,1,4 in no particular order. In order to maximize our product, we can do 5^4 x 3^2 x 2^1=11250

$\endgroup$
0
$\begingroup$

Because it must be a multiple of $30 = 2 \cdot 3 \cdot 5$, then the number must be of the form $$N = 2^{\alpha+1} \cdot 3^{\beta+1} \cdot 5^{\gamma+1} \cdot M $$ where $M$ is $1$ or a product of primes that are greater than $5$ and $\alpha, \beta$, and $\gamma$ are non negative integers.

Let $d(n)$ represent the number of different positive divisors of $n$. Then

$$d(N) = (\alpha+2)(\beta +2)(\gamma + 2)d(M)$$

and $d(N)$ is a multiple of $30 = 2 \cdot 3 \cdot 5$. It follows that $\{\alpha+2, \beta+2, \gamma+2\} = \{2,3,5\}$ and $d(M)=1$. The largest value of $N$ will occur when $\alpha = 0, \beta = 1$, and $\gamma = 3$. The value of $N$ is therefore

$$N = 2^1 \cdot 3^2 \cdot 5^4 = 11250$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .