# Find least possible number of factors

Number $A$ has $24$ factors. Number $A\cdot B$ has $105$ factors. Find least possible number of factors of $B$. I have tried. But there seems to be no general approach.. The answer given is $12$.

• The hint given in the book is like this: Try to take as much common factors in A and B as possible. I don't see why Jan 5, 2015 at 11:07
• Hint: A number could be a factor of AB if and only if it is either a factor of A, a factor of B, or a product of two such factors. Jan 5, 2015 at 11:32
• Are there statements about the distinctness of factors? Jan 5, 2015 at 11:38
• No other information. Jan 5, 2015 at 11:41
• If by "factors" to mean "non-distinct prime factors", then $B$ has exactly $105-24$ factors (no more, no less). So I assume that you mean "distinct prime factors"... Is that correct? Jan 5, 2015 at 12:22

If $m$ is a number that can be factored to

$$m=p_1^{e_1} \cdot p_2^{e_2} \cdots p_n^{e_n}$$

then $m$ has $(e_1+1)(e_2+2) \cdots (e_n+n)$ divisors. $A$ has $24=2^3 \cdot 3$ divisors, so $A$ can have at most $4$ prime factors, e.g.

$$A=p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot p_4^{e_4}$$

If $A$ would have $4$ prime factors then $AB$ would have at least $4$ prime factors. But $AB$ has $105=3 \cdot 5 \cdot 7$ divisors so it has at most $3$ prime factors. The prime factors of $A$ are contained in $AB$ so $A$ does have equal or less prime factors than $AB$. We assume that $AB$ has the representation $$AB = p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \tag{1}$$ If $AB$ is factored only in two or one different prime factors then we add one or two arbitrary prime factors to the representation of $AB$ with the exponent $0$. $A$ has an analog representation with same $p_i$ but maybe different exponents $e_i$ We choose the indexes of the prime $p_1, P_2, p_3$ so that $e_1 \le e_2 \le e_3$ for the exponents $e_i$ in the representation of $A$ and $p_i \le p_{i+1}$ if $e_i=e_{i+1}$. Because $24=(e1+1)(e2+1)(e3+1)$ and $(e1+1) \le (e2+1) \le (e3+1)$ we have the following possibilities for the $(e_i+1)$ of $A$

A
e1+1 e2+1 e3+1
2    2     6
2    3     4
1    2    12
1    3     8
1    4     6
1    1    24


For $AB$ we have the this possibilities (we cannot assume that $(e1+1) \le (e2+1) \le (e3+1)$ for the exponents of the factorisation of $AB$).


AB
e1+1 e2+1 e3+1
3    5    7
3    7    5
5    3    7
5    7    3
7    3    5
7    5    3
3   35    1
35    3    1
1    3   35
1   35    3
3    1   35
35    1    3
5   21    1
21    5    1
1    5   21
1   21    5
5    1   21
21    1    5
7   15    1
15    7    1
1    7   15
1   15    7
7    1   15
15    1    7
105    1    1
1  105    1
1    1  105


Now we combine these tables and calculate

$$e_i+1 \;\text{of}\; B = (e_i+1 \;\text{of} \;AB)-(e_i+1 \;\text{of}\; A)+1$$

Basically we have to check $6 \cdot 27$ combinations of possible representations of $A$ and of $AB$. But we can ignore representation where $A$ has a higher exponent than $AB$. Finally the following possibilities remain:


A               AB              B               B
e1+1 e2+1 e3+1  e1+1 e2+1 e3+1  e1+1 e2+1 e3+1  prod
2    2    6     3    5    7     2    4    2    16
2    2    6     5    3    7     4    2    2    16
2    3    4     3    5    7     2    3    4    24
2    3    4     3    7    5     2    5    2    20
2    3    4     5    3    7     4    1    4    16
2    3    4     7    3    5     6    1    2    12
1    2   12     1    3   35     1    2   24    48
1    2   12     1    5   21     1    4   10    40
1    2   12     1    7   15     1    6    4    24
1    3    8     1    3   35     1    1   28    28
1    3    8     1    5   21     1    3   14    42
1    3    8     1    7   15     1    5    8    40
1    4    6     3    5    7     3    2    2    12
1    4    6     1    5   21     1    2   16    32
1    4    6     1    7   15     1    4   10    40
1    4    6     1    15   7     1   12    2    24
1    1   24     1    3   35     1    3   12    36
1    1   24     3    1   35     3    1   12    36
1    1   24     1    1  105     1    1   82    82


prod is the number of factors of $B$. The minimal value in this column is $12$

• This is a multiple choice question. I think there ought to be some shortcut. Jan 5, 2015 at 14:30
• Where can I see that this is a multiple choice question? Jan 5, 2015 at 14:33
• Sorry for that. But thanks for the help. But can you think of any idea how to solve this within time. Jan 5, 2015 at 14:42
• @archangel89: It is quite possible that knowledge of the multiple choices available makes the problem simpler, even if the logic of the Answer above is applied. That is, it might be possible to quickly eliminate all but one choice using the arguments given above. Since you did not share the particulars of any multiple choices, you are in the best position to evaluate this for now. Jan 5, 2015 at 15:17

Let $n=AB=\prod_{j=1}^{k}p_j^{n_j},$ then the number of divisors is $\sigma(n)=\prod_{j=1}^k(n_j+1)=105.$ So $k=3.$ Let $A=\prod_{j=1}^{3}p_j^{a_j},\ B=\prod_{j=1}^{3}p_j^{b_j}.$ Then $\sigma(A)=(a_1+1)(a_2+1)(a_3+1)=24$ and $\sigma(B)=(b_1+1)(b_2+1)(b_3+1).$ We have $a_j+b_j=n_j$ (and so $0\leq a_j,b_j\leq n_j$) and without loss of generality $(n_1+1,n_2+1,n_3+1)=(3,5,7).$ So $$(a_1,a_2,a_3)\in \{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(0,3,5),(1,1,5)\}.$$ This gives the following values for $$\sigma(B)=[(n_1+1)-a_1][(n_2+1)-a_2][(n_3+1)-a_3]=$$ $$(3-a_1)(5-a_2)(7-a_3)\in \{24,20,16,{\bf 12},{\bf 12},16\}.$$ $\small{\text{(hope not to forget something)}}$

• you cannot assume that $AB has exactly three prime factors. It is possible that it has only two or one prime factor. Jan 5, 2015 at 14:04 • Due to the constraints of the problem you cannot have$k=1$or$2$and 12 divisors for$B.$– 111 Jan 5, 2015 at 14:27 • Due to what constraint? Jan 5, 2015 at 14:29 A partial answer : The number$2^2\times3^4\times5^6$has$105$factors, the number$3^3\times5^5$has$24$factors and the number$2^2\times3\times5$has$12$factors. So, there is an example, such that$B$has$12$factors. • What is the approach? Jan 5, 2015 at 11:39 • The number of divisors of$p_1^{n_1}...p_k^{n_k}$is$(n_1+1)...(n_k+1)$. So, if the exponents are$2,4,6$, then the number will have$105$factors. To get$24$factors, you can choose the exponents$3,5$. The fraction of these two numbers (assuming the same primes as bases) has the exponents$2,1,1$, so it will have$12$factors. Jan 5, 2015 at 11:40 • To be exact, the second number has exponents$0,3,5$($0$corresponds to the prime$2$), so the differences of the exponents are$2,1,1$. Jan 5, 2015 at 11:47 • If this reasoning is correct I cannot see how there can be more than 12 factors of$B$. Jan 5, 2015 at 11:50 • If you subtract 24 from 105 you get 81. If you divide 81 by 24 you get 3 remainder 9, and if you add those, you get 12... Was this just a lucky guess by me or is there a connection? I'm not that much into number theory... Jan 5, 2015 at 11:54 The general approach is this (example given with$24$and$105$): •$24=6\cdot4\implies{p^{6-1}}\cdot{q^{4-1}}$has$24$divisors •$105=7\cdot5\cdot3\implies{p^{7-1}}\cdot{q^{5-1}}\cdot{r^{3-1}}$has$105$divisors •$\dfrac{{p^{7-1}}\cdot{q^{5-1}}\cdot{r^{3-1}}}{{p^{6-1}}\cdot{q^{4-1}}}={p^{2-1}}\cdot{q^{2-1}}\cdot{r^{3-1}}$has$2\cdot2\cdot3=12$divisors Any distinct primes$[p,q,r]$that you choose will gave you the same number of divisors. Each one of the following is a valid combination of A and AB:  | 105 | 3*35 | 5*21 | 7*15 | 3*5*7 ---------|-------|-------|-------|-------|------- 24 | | | X | X | X ---------|-------|-------|-------|-------|------- 2*12 | X | | | | X ---------|-------|-------|-------|-------|------- 3*8 | X | | | | X ---------|-------|-------|-------|-------|------- 4*6 | X | X | | | V ---------|-------|-------|-------|-------|------- 2*2*6 | X | X | X | X | ---------|-------|-------|-------|-------|------- 2*3*4 | X | X | X | X | ---------|-------|-------|-------|-------|------- 2*2*2*3 | X | X | X | X | X  In the combinations marked X, the value of B will not be integer. In general, you should try each of the other combinations in order to find out which one yields a value of B with the lowest number of divisors (the combination marked V is the one that I tested). • you are missing a lot of other cases you have to check Jan 5, 2015 at 14:16 • @miracle173: Of course, you need to go through every factorization of each number, and then filter out the "minimal" quotient (I updated the answer accordingly). Jan 5, 2015 at 16:35 Let$A = p_1 ^ {k_1} \times p_2 ^ {k_2} ... p_n ^ {k_n}$So$24 = (k_1 + 1) \times (k_2 + 1) ... (k_n +1)$Let$B = p_1 ^ {l_1} \times p_2 ^ {l_2} ... p_n ^ {l_n} \times q_1 ^ {m_1} \times q_2 ^ {m_2} ... q_v ^ {m_v} ...$allowing for some$l_i$'s to be$0$if necessary. Then$105 = ({k_1} + {l_1} + 1) \times ({k_2} + {l_2} + 1) ... ({k_n} + {l_n} + 1) \times ({m_1} + 1) .. ({m_v} + 1)$But 105 = 3 x 5 x 7 ... So n <= 3 Case 1: n=1,$ A = p^{23}$... most economical$AB = p ^ {34} \times q ^ 2 $with B having 12 x 3 = 36 factors Case 2: n=2 i.$A = {p_1} ^ {11} \times {p_2} ^ 1$... most economical$AB = {p_1} ^ {14} \times {p_2} ^ 6$with B having 4 x 6 = 24 factors ii.$A = {p_1} ^ 7 \times {p_2} ^ 2$... most economical$AB = {p_1} ^ {14} x {p_2} ^ 6$with B having 8 x 5 = 40 factors iii.$A = {p_1} ^ 5 \times {p_2} ^ 3$... most economical$AB = {p_1} ^ 6 \times {p_2} ^ 4 \times q ^ 2$with B having 12 factors Case 3 n=3 i.$ A = {p_1} ^ 5 \times {p_2} ^ 1 \times {p_3}$... most economical$AB = {p_1} ^ 6 \times {p_2} ^ 2 \times {p_3} ^ 4$with B having 16 factors ii.$A = {p_1} ^ 3 \times {p_2} ^ 2 \times {p_3}$... most economical$AB = {p_1} ^ 4 \times {p_2} ^ 2 \times {p_3} ^ 6\$ with B having 12 factors also

This search is exhaustive which completes the proof.

• What is most economical AB? I have understood but still would be better if you make clarifications. Jan 5, 2015 at 13:57
• It would be nice if you can change it to a readable format using latex. I did the first few lines for you as an exapmle. Jan 5, 2015 at 14:15