Take the product of all positive divisors of 100: $1 \times 2 \times 4 \times 5 \times \cdots \times 100 .$
This product is divisible by some $2^m ,$ where $m$ is an integer. What is the largest possible value of $m?$
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
nonjavascript version of this page
. We're sorry about the hassle.
how does this prove that the answer is 9?
Log in to reply
I liked that!!! Think that the numbers he describes can be devided with 2 as much times as he says in the second column.Also the greatest devisor of the number above cant be greater than the greatest devisor of the multiply of the numbers devided with 2, that take part in the multiplication. So m is the sum of the second column
Hi Abigail, Alex is right, I hope his answer made things clearer. Also if you look below Zach S has posted a solution using the same reasoning but he has provided a bit more detail.
As we know that from number theory, the product of positive divisors of $n∈N =n^{\frac{τ(n)}{2}}$ where $τ(n)=$ number of positive divisors of $n∈N$ .
So, the product of positive divisors of
$100$
is
$= 100^{\frac{τ(100)}{2}}$
$= 100^{\frac{9}{2}}$
$= (2^2 × 5^2)^{\frac{9}{2}}$
$= 2^9 × 5^9$
Which clearly imply the product is divisible by
$2^9$
so that
$m=9$
Edit : adding more details about τ(n)= number of divisors of $n∈N$ .
To find τ(n) First express $n$ in the prime factorization form! Say,
$n= p^a × q^b × r^c ×...$ where $p,q,r,....$ are prime numbers! then,
$τ(n)= (a+1)(b+1)(c+1)....$
So that, $τ(100) = τ(2^2 × 5^2)=(2+1)(2+1)=9$
if we break it as: $1.2.3.4.5.6.7.8.9.10.11.12=1.(2).3.(2^2).5.(2).3.7.(2^3).9.(2).5.11.(2^2).3=(2^{10}).1.3.5.3.7.9.5.11.3$ only till here i have got m=10, so the answer must be larger.
Log in to reply
the question asked to multiply all divisors of 100 , not all numbers upto a hundred, so $1 \times 2 \times 4 \times 5 \times 10 \times 20 \times 25 \times 50 \times 100$
Log in to reply
What you dont get is that the numbers have to be divisible by 2. So either you multiply those 7 numbers 1X2X4X10X20X50X100 = 8,000,000. Or 1X2X4X5X10X20X25X50X100 9 numbers. so 2^9 = 512.
Ashok, i did the same mistake as you did. Glad you asked :P
where did you find the function tau  which gave the 9? because that was the trick. Unless you brute forced it, which isn't fun at all xD.
Log in to reply
See any number theory book you will find it. First express $n$ in the prime factorization form! Say,
$n= p^a × q^b × r^c ×...$ where $p,q,r,....$ are prime numbers! then,
$τ(n)= (a+1)(b+1)(c+1)....$
So that, $τ(100) = τ(2^2 × 5^2)=(2+1)(2+1)=9$
Generalization : $\begin{aligned} N & = p_1^{e_1}\cdot p_2^{e_2}\cdots p_n^{e_n} & \text{prime decomposition of a number}\ N \\ D & = \prod_{\stackrel{d\geq 1}{dN}} d & \text{product of its divisors} \\ D & = p_1^{m_1}\cdot p_2^{m_2}\cdots p_n^{m_n} & \text{its prime content} \\ m_i & = \tfrac12e_i \cdot \prod_{j=1}^n (e_j+1) & \text{maximum power of}\ p_i.\end{aligned}$
In this case, $100 = N = 2^2\cdot 5^2$ ; so $m = \tfrac12\cdot 2\cdot (2+1)\cdot (2+1) = \boxed{9}.$
I’m amazed you can give a general solution! Could you provide a term or keywords that would help people to look up the derivation of the formula? Many thanks!
Log in to reply
Look for the divisor count formula .
Specifically, let $N = p_i^{e_i}\cdot M$ , where $p_i$ is the prime factor of interest and $M$ is $p$ free. Then the divisors of $N$ are precisely the set $\{p_i^k\cdot D\ \ 0 \leq k \leq e_i\ \text{and}\ D\ \text{is a divisor of}\ M\}.$ Let $s$ be the number of divisors of $D$ ; then this set contains $s$ divisors involving $p_i^k$ for each value of $k$ . Therefore $m = \sum_{k=0}^{e_i} sk = s \sum_{k=0}^{e_i} k = s \cdot \tfrac12 e_i(e_i + 1).$ Finally, from the divisor count formula , $s = \prod (1 + e_j)$ summed over all other prime factors; thus $m = \prod_{j \not= i} (1 + e_j)\cdot \tfrac12 e_i(e_i + 1),$ and by absorbing the factor $e_i+1$ in the product, we finally get $m = \prod_{j} (1 + e_j)\cdot \tfrac12 e_i.$
A simple "handwaving" argument is that each divisor contributes on average $\tfrac 12 e_i$ factors $p_i$ . Since the number of divisors is $\tau(N) = \prod (1 + e_j)$ , the formula follows.
why is 3 absent in the problem statement? 1 x 2 x 4 x 5
but you are taking about 100 or 100! ???
Log in to reply
I was talking about $N = 100 = 2^2\cdot 5^2$ and $D = 1 \times 2\times 4\times 5 \times 10 \times 20\times 25 \times 50 \times 100 = 2^9\cdot 5^9.$
$100!$ plays no role in this problem.
The positive divisors of 100 are 1, 2, 4, 5, 10, 20, 25, 50, and 100.
Using prime factorization:
$2=2^1$
$4=2^2$
$5=5^1$
$10=2^1\cdot5^1$
$20=2^2\cdot5^1$
$25=5^2$
$50=2^1\cdot5^2$
$100=2^2\cdot5^2$
Because we are multiplying these factors together, we can add identical numbers' powers. Thus, our product is equal to $1 \cdot 2^9 \cdot 5^9$
And we can easily see that the largest $2^m$ number that this product is divisible by is $2^9$
$m=9$
Çok mükemmel bir karıştırarak pişirin bir hava var kendi iyi gemi ile bir karıştırarak kavurun bir hava katacak ve buz pateni açıklaması yaptı bu w
Note that there are 9 total divisors $d$ of 100 . Total divisors $1 \leq d \leq 100$ are $1, 2, 4, 5, 10 , 20, 25, 50, 100$ . $\begin{aligned}& \therefore P_{100} = 1\times 2\times 4 \times 5 \times 10 \times 20 \times 25 \times 50 \times 100 =2^9 \times k \end{aligned}$ Hence required highest integer value for $m =9$
A constant divided by an exponential function has no maximum
Log in to reply
1000000000 divided by 2^m where m is an integer. Consider this as a function and graph it. As m approaches infinity the function approaches 0, there is no maximum value of m.....1000000000 divided by 2^999999999999999999999999 however close to 0 is still not 0 but none the less exists
The divisors of 100 is 1,2,4,5,10,20,25,50,100. And their product is 200,000,000 or 2x10^8 which is 2x(2x5)^8 = 2^9x5^8. And the largest power of two that is a divisor of the product of the divisors of 100 is 9
Positive divisors of 100 are:
1, 2, 4, 5, 10, 20, 25, 50, 100.
So by factorizing each of them we get:
1= 2^0
2= 2^1
4= 2^2
5= 5 × 2^0
10= 5 × 2^1
20= 5 × 2^2
25= 5^2 × 2^0
50= 5^2 × 2^1
100= 5^2 × 2^2.
We need to take their product that will consist of adding all the powers of 5 and 2. Since, 2^m divides the product so the maximum value for m can be the power of 2 obtained on factorizing the product. As we know on multiplication the power of common bases get adds up , therefore, largest value for m = 9 .
We can express 5 as 2^2 + 1
100 = 5^2x2^2 or 5x5x2x2, so only the combinations of 5 and 2 from exp 0 to exp 2 can be divisors. Then I thought that I could put all possible combinations in a table, so:
BASE 3:
Twos  Fives 
0  0 
0  1 
0  2 
1  0 
1  1 
1  2 
2  0 
2  1 
2  2 
And I count all the twos (the first column) 0+0+0+1+1+1+2+2+2=9 So 2^9 is the maximum 2^m
m = 9
The general expresion to 10^n would be (n+1)^2 • n/2
1000000000 divided by 2^97 is a real number 6.31 x 10^21...the constrainst of the problem only require m to be an integer and the quotient to exist
Log in to reply
You mean all the divisors of 1000000000? In that case I would use base 10 (from 0 to 9 since the top number is 2^9x5^9) and I would put the possible exponents in a similar list (with 100 terms, 10 options of 2^(something) and 10 options of 5^(something)) and I would count all the possible exponents for 2. For each 2^(something) I have 10 different options of 5's multiplying (from 0 (nothing, x1) to 9 (5^9)), and thus I have 0x10+1x10+...+9x10 in total. I am playing with the exponents of numbers multiplying so I will sum up all the exponents, and I get 450. m=450
As $100=2^2\cdot5^2$ , every factor of 100 will be of the form $2^{k_{1}}\cdot5^{k_{2}}$ , where $0 \le k_{1},k_{2} \le 2$ . The three factors for which $k_{1}=0$ will contribute no 2's, the three factors for which $k_{1}=1$ will each contribute one 2 (for a combined contribution of $2^3)$ , and the three factors for which $k_{1}=2$ will each contribute two 2's (for a combined contribution of $2^6)$ . Thus the total contribution of all factors will be $2^9$ , so that will be the highest power of 2 dividing the product in question.
List all the factors: 1, 2, 4, 5, 10, 20, 25, 50, 100
Regroup the possible combinations: 1x100 = 100  2x50 = 100  4x25 = 100  5x20 = 100  10 = 10
By counting the number of "0"s, we know that the product of all factors is 10^9
Break down the product into a combination of 2 times 5: "10^9 = 2^9 x 5^9"
This shows that the maximum value for m in 2^m is 9
By filling in the blanks, we would have the product of all the positive divisors of 100 listed as: 1 x 2 x 4 x 5 x 10 x 20 x 25 x 50 x 100. By using prime factorization of each of these we can rewrite this product as 1 x 2 x $2^2$ x 5 x $2*5$ x $2^2 * 5$ x $5^2$ x $2*5^2$ x $2^2 * 5^2$ . Then we see that $2^9$ would be a factor of this product.
$100 = 2^2×5^2$ , thus, 100 has (2+1)(2+1) = 9 divisors. From these, only 1, 5 and 25 are not multiples of 2 ( $5^0, 5^1, 5^2$ respectively). This means there are 6 multiples of two in the product. But then, we've got to count one 2 more for each multiple of four, which are 4, 20 and 100 ( $2^2, 2^2×5, 2^2×5^2$ respectively) so there are three 2s more to count. It is easy to see there are no multiples of other powers of two in this product, so it is divisible by $2^{6+3} = 2^9$ , and we can see that 9 is maximum $m$ . Hence, the answer is $\boxed 9$ .
Here's one I haven't read here (maybe I was just too lazy). We can combine the Divisors in pairs: 1x100, 2x50, 4x25, 5x20 and 10x10. As all these Products are 100 we see that in each pair the factor 2 occurs twice however we only have one 10 so we subtract the one two we counted double. 5x21=9
First, we consider all the divisors that are of the form $2^1\cdot k$ where $k\nmid 2$ . There are three values of $k$ that are divisors of $100$ : $k=1,5,25$ . Thus, three divisors have $2^1$ as a factor. Similarly, with the same values of $k$ , there are three divisors of the form $2^2\cdot k$ . Adding together the exponents of all these divisors, we get $m=1\cdot 3+2\cdot 3=9.$
(1 * 2 * 4 * 5 ... * 100)/2^m = ((25^3) * (5^3))/2^(m9) Therefore m=9
$100$ can be written as $2^2\times5^2$ . The powers of two can be generated with two cases: $2\times5^n$ or $2^2\times5^n$ . The first case has $3$ powers of 2 because there are $3$ ways to multiply a power of five by 2, those ways being $5^0,5^1,$ and $5^2$ . The second case has $2\times3=6$ powers of 2 because there are three ways to multiply a power of five by 2, then doubled because we are multiplying by a power of $2$ . Adding these cases up gets us a solution of $3+6=$ 9 .
Positive divisors of 100: 1, 2, 4, 5, 10, 20, 25, 50, 100
Product of the positive divisors of 100 = $1 \cdot 2 \cdot 4 \cdot 5 \cdot 10 \cdot 20 \cdot 25 \cdot 50 \cdot 100 = 10^9$
We know that, $1000 = 10^3 = 8 \cdot 125 = 2^3 \cdot 5^3$
Therefore, $10^9 = (10^3)^3 = (2^3 \cdot 5^3)^3 = 2^9 \cdot 5^9$
Hence, m = 9 .
Matlab solution: sum(mod(prod(divisors(100)),2.^[1:100])==0)
Another programmatic solution (JavaScript):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 

1 

Mathematica
Here are the prime factors of the final product
FactorInteger[Times @@ Divisors@100]
{{2, 9}, {5, 9}}
which means
*2^9 * 5^9 *
Problem Loading...
Note Loading...
Set Loading...
Consider the multiples of two in the prime factors of each divisor. These will determine the number of 2s in the product. We can ignore 1, 5, and 25 as they are not multiples of two.
Thus there are 9 in total.