# Let be N the smallest integer with 378 divisors. If N = 2^a xx 3^b xx 5^c xx 7^d, what is the value of {a,b,c,d} in NN ?

##### 1 Answer
Oct 4, 2016

$\left(a , b , c , d\right) = \left(6 , 5 , 2 , 2\right)$

$N = {2}^{6} \times {3}^{5} \times {5}^{2} \times {7}^{2} = 19 , 051 , 200$

#### Explanation:

Given a number $n$ with prime factorization $n = {p}_{1}^{{\alpha}_{1}} {p}_{2}^{{\alpha}_{2}} \ldots {p}_{k}^{{\alpha}_{k}}$, each divisor of $n$ is of the form ${p}_{1}^{{\beta}_{1}} {p}_{2}^{{\beta}_{2}} \ldots {p}_{k}^{{\beta}_{k}}$ where ${\beta}_{i} \in \left\{0 , 1 , \ldots , {\alpha}_{i}\right\}$. As there are ${\alpha}_{i} + 1$ choices for each ${\beta}_{i}$, the number of divisors of $n$ is given by
$\left({\alpha}_{1} + 1\right) \left({\alpha}_{2} + 1\right) \ldots \left({\alpha}_{k} + 1\right) = {\prod}_{i = 1}^{k} \left({\alpha}_{i} + 1\right)$

As $N = {2}^{a} \times {3}^{b} \times {5}^{c} \times {7}^{d}$, the number of divisors of $N$ is given by $\left(a + 1\right) \left(b + 1\right) \left(c + 1\right) \left(d + 1\right) = 378$. Thus, our goal is to find $\left(a , b , c , d\right)$ such that the above product holds and ${2}^{a} \times {3}^{b} \times {5}^{c} \times {7}^{d}$ is minimal. As we are minimizing, we will assume from this point onward that $a \ge b \ge c \ge d$ (if this were not the case, we could swap exponents to get a lesser result with the same number of divisors).

Noting that $378 = 2 \times {3}^{3} \times 7$, we can consider the possible cases in which $378$ is written as a product of four integers ${k}_{1} , {k}_{2} , {k}_{3} , {k}_{4}$. We can inspect these to see which produces the least result for $N$.

Format: $\left({k}_{1} , {k}_{2} , {k}_{3} , {k}_{4}\right) \implies \left(a , b , c , d\right) \implies {2}^{a} \times {3}^{b} \times {5}^{c} \times {7}^{d}$

(2, 3, 3^2, 7) => (8, 6, 2, 1) => ~3.3xx10^7
(2, 3, 3, 3*7) => (20, 2, 2, 1) => ~1.7xx10^9
color(red)((3, 3, 2*3, 7) => (6, 5, 2, 2) => ~1.9xx10^7)
(3, 3, 3, 2*7) => (13, 2, 2, 2) => ~9.0xx10^7
(1, 3, 2*3^2, 7) => (17, 6, 2, 0) => ~2.4xx10^9

We can stop here, as any further cases will have some ${k}_{i} \ge 27$, giving ${2}^{a} \ge {2}^{26} \approx 6.7 \times {10}^{7}$, which is already greater than our best case.

By the above work, then, the $\left(a , b , c , d\right)$ which produces a minimal $N$ with $378$ divisors is $\left(a , b , c , d\right) = \left(6 , 5 , 2 , 2\right)$, giving $N = {2}^{6} \times {3}^{5} \times {5}^{2} \times {7}^{2} = 19 , 051 , 200$