# 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 – archangel89 Jan 5 '15 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. – Shai Deshe Jan 5 '15 at 11:32
• Are there statements about the distinctness of factors? – user2103480 Jan 5 '15 at 11:38
• No other information. – archangel89 Jan 5 '15 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? – barak manos Jan 5 '15 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. – archangel89 Jan 5 '15 at 14:30
• Where can I see that this is a multiple choice question? – miracle173 Jan 5 '15 at 14:33
• Sorry for that. But thanks for the help. But can you think of any idea how to solve this within time. – archangel89 Jan 5 '15 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. – hardmath Jan 5 '15 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. – miracle173 Jan 5 '15 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 '15 at 14:27 • Due to what constraint? – miracle173 Jan 5 '15 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? – archangel89 Jan 5 '15 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. – Peter Jan 5 '15 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$. – Peter Jan 5 '15 at 11:47 • If this reasoning is correct I cannot see how there can be more than 12 factors of$B$. – Suzu Hirose Jan 5 '15 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... – user2103480 Jan 5 '15 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 – miracle173 Jan 5 '15 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). – barak manos Jan 5 '15 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. – archangel89 Jan 5 '15 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. – miracle173 Jan 5 '15 at 14:15