2 2 s in Divisor Product of 100 100

Take the product of all positive divisors of 100: 1 × 2 × 4 × 5 × × 100. 1 \times 2 \times 4 \times 5 \times \cdots \times 100 .

This product is divisible by some 2 m , 2^m , where m m is an integer. What is the largest possible value of m ? m?


The answer is 9.

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 non-javascript version of this page . We're sorry about the hassle.

21 solutions

Robert Williams
Mar 4, 2018

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.

Divisor Multiples of 2
2 1
4 2
10 1
20 2
50 1
100 2

Thus there are 9 in total.

how does this prove that the answer is 9?

Abigail Keenan - 3 years, 3 months ago

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

alex spit - 3 years, 2 months ago

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.

Robert Williams - 3 years, 2 months ago

As we know that from number theory, the product of positive divisors of n N = n τ ( n ) 2 n∈N =n^{\frac{τ(n)}{2}} where τ ( n ) = τ(n)= number of positive divisors of n N n∈N .

So, the product of positive divisors of 100 100 is = 10 0 τ ( 100 ) 2 = 100^{\frac{τ(100)}{2}}
= 10 0 9 2 = 100^{\frac{9}{2}}
= ( 2 2 × 5 2 ) 9 2 = (2^2 × 5^2)^{\frac{9}{2}} = 2 9 × 5 9 = 2^9 × 5^9 Which clearly imply the product is divisible by 2 9 2^9 so that m = 9 m=9

Edit : adding more details about τ(n)= number of divisors of n N n∈N .

To find τ(n) First express n n in the prime factorization form! Say,

n = p a × q b × r c × . . . n= p^a × q^b × r^c ×... where p , q , r , . . . . p,q,r,.... are prime numbers! then,

τ ( n ) = ( a + 1 ) ( b + 1 ) ( c + 1 ) . . . . τ(n)= (a+1)(b+1)(c+1)....

So that, τ ( 100 ) = τ ( 2 2 × 5 2 ) = ( 2 + 1 ) ( 2 + 1 ) = 9 τ(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 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.

Aaryan Maheshwari - 3 years, 3 months ago

Log in to reply

the question asked to multiply all divisors of 100 , not all numbers upto a hundred, so 1 × 2 × 4 × 5 × 10 × 20 × 25 × 50 × 100 1 \times 2 \times 4 \times 5 \times 10 \times 20 \times 25 \times 50 \times 100

Aareyan Manzoor - 3 years, 3 months ago

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.

Alex Nieves - 3 years, 2 months ago

Ashok, i did the same mistake as you did. Glad you asked :P

sandeep prakash - 3 years, 3 months ago

Log in to reply

So did I. I got 97

simon simon - 3 years, 1 month ago

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.

Gonçalo Felício - 3 years, 3 months ago

Log in to reply

See any number theory book you will find it. First express n n in the prime factorization form! Say,

n = p a × q b × r c × . . . n= p^a × q^b × r^c ×... where p , q , r , . . . . p,q,r,.... are prime numbers! then,

τ ( n ) = ( a + 1 ) ( b + 1 ) ( c + 1 ) . . . . τ(n)= (a+1)(b+1)(c+1)....

So that, τ ( 100 ) = τ ( 2 2 × 5 2 ) = ( 2 + 1 ) ( 2 + 1 ) = 9 τ(100) = τ(2^2 × 5^2)=(2+1)(2+1)=9

akash patalwanshi - 3 years, 3 months ago

Generalization : N = p 1 e 1 p 2 e 2 p n e n prime decomposition of a number N D = d N d 1 d product of its divisors D = p 1 m 1 p 2 m 2 p n m n its prime content m i = 1 2 e i j = 1 n ( e j + 1 ) maximum power of p i . \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}{d|N}} 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 5 2 100 = N = 2^2\cdot 5^2 ; so m = 1 2 2 ( 2 + 1 ) ( 2 + 1 ) = 9 . 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!

Robert Williams - 3 years, 3 months ago

Log in to reply

Look for the divisor count formula .

Specifically, let N = p i e i M N = p_i^{e_i}\cdot M , where p i p_i is the prime factor of interest and M M is p p -free. Then the divisors of N N are precisely the set { p i k D 0 k e i and D is a divisor of M } . \{p_i^k\cdot D\ |\ 0 \leq k \leq e_i\ \text{and}\ D\ \text{is a divisor of}\ M\}. Let s s be the number of divisors of D D ; then this set contains s s divisors involving p i k p_i^k for each value of k k . Therefore m = k = 0 e i s k = s k = 0 e i k = s 1 2 e i ( e i + 1 ) . 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 = ( 1 + e j ) s = \prod (1 + e_j) summed over all other prime factors; thus m = j i ( 1 + e j ) 1 2 e i ( e i + 1 ) , m = \prod_{j \not= i} (1 + e_j)\cdot \tfrac12 e_i(e_i + 1), and by absorbing the factor e i + 1 e_i+1 in the product, we finally get m = j ( 1 + e j ) 1 2 e i . m = \prod_{j} (1 + e_j)\cdot \tfrac12 e_i.

Arjen Vreugdenhil - 3 years, 3 months ago

Log in to reply

Thank you very much!!!

Robert Williams - 3 years, 3 months ago

A simple "hand-waving" argument is that each divisor contributes on average 1 2 e i \tfrac 12 e_i factors p i p_i . Since the number of divisors is τ ( N ) = ( 1 + e j ) \tau(N) = \prod (1 + e_j) , the formula follows.

Arjen Vreugdenhil - 3 years, 3 months ago

why is 3 absent in the problem statement? 1 x 2 x 4 x 5

Greg Hill - 3 years, 3 months ago

Log in to reply

Because 3 is not a divisor of 100.

Arjen Vreugdenhil - 3 years, 3 months ago

but you are taking about 100 or 100! ???

Luis Guardado - 3 years, 2 months ago

Log in to reply

I was talking about N = 100 = 2 2 5 2 N = 100 = 2^2\cdot 5^2 and D = 1 × 2 × 4 × 5 × 10 × 20 × 25 × 50 × 100 = 2 9 5 9 . D = 1 \times 2\times 4\times 5 \times 10 \times 20\times 25 \times 50 \times 100 = 2^9\cdot 5^9.

100 ! 100! plays no role in this problem.

Arjen Vreugdenhil - 3 years, 2 months ago
Zachary Stewart
Mar 5, 2018

The positive divisors of 100 are 1, 2, 4, 5, 10, 20, 25, 50, and 100.

Using prime factorization:

2 = 2 1 2=2^1

4 = 2 2 4=2^2

5 = 5 1 5=5^1

10 = 2 1 5 1 10=2^1\cdot5^1

20 = 2 2 5 1 20=2^2\cdot5^1

25 = 5 2 25=5^2

50 = 2 1 5 2 50=2^1\cdot5^2

100 = 2 2 5 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 2 9 5 9 1 \cdot 2^9 \cdot 5^9

And we can easily see that the largest 2 m 2^m number that this product is divisible by is 2 9 2^9

m = 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

Ece Erdogan - 3 years, 3 months ago
Naren Bhandari
Feb 25, 2018

Note that there are 9 total divisors d d of 100 . Total divisors 1 d 100 1 \leq d \leq 100 are 1 , 2 , 4 , 5 , 10 , 20 , 25 , 50 , 100 1, 2, 4, 5, 10 , 20, 25, 50, 100 . P 100 = 1 × 2 × 4 × 5 × 10 × 20 × 25 × 50 × 100 = 2 9 × k \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 m =9

A constant divided by an exponential function has no maximum

Jerry Duncan - 3 years, 3 months ago

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

Jerry Duncan - 3 years, 3 months ago
William Oliver
Mar 5, 2018

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

Dhruv Mehta
Mar 8, 2018

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

Jerry Duncan - 3 years, 3 months ago
Ruben Jimenez
Mar 8, 2018

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

Jerry Duncan - 3 years, 3 months ago

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

Ruben Jimenez - 3 years, 3 months ago
Zico Quintina
Mar 6, 2018

As 100 = 2 2 5 2 100=2^2\cdot5^2 , every factor of 100 will be of the form 2 k 1 5 k 2 2^{k_{1}}\cdot5^{k_{2}} , where 0 k 1 , k 2 2 0 \le k_{1},k_{2} \le 2 . The three factors for which k 1 = 0 k_{1}=0 will contribute no 2's, the three factors for which k 1 = 1 k_{1}=1 will each contribute one 2 (for a combined contribution of 2 3 ) 2^3) , and the three factors for which k 1 = 2 k_{1}=2 will each contribute two 2's (for a combined contribution of 2 6 ) 2^6) . Thus the total contribution of all factors will be 2 9 2^9 , so that will be the highest power of 2 dividing the product in question.

Michael Cheung
Mar 6, 2018

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

Will Enny
Mar 6, 2018

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 2^2 x 5 x 2 5 2*5 x 2 2 5 2^2 * 5 x 5 2 5^2 x 2 5 2 2*5^2 x 2 2 5 2 2^2 * 5^2 . Then we see that 2 9 2^9 would be a factor of this product.

Javier Álvarez
Mar 5, 2018

100 = 2 2 × 5 2 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 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 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 2^{6+3} = 2^9 , and we can see that 9 is maximum m m . Hence, the answer is 9 \boxed 9 .

Freddy Fi
Mar 11, 2018

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. 5x2-1=9

Nathan Chasse
Mar 10, 2018

First, we consider all the divisors that are of the form 2 1 k 2^1\cdot k where k 2 k\nmid 2 . There are three values of k k that are divisors of 100 100 : k = 1 , 5 , 25 k=1,5,25 . Thus, three divisors have 2 1 2^1 as a factor. Similarly, with the same values of k k , there are three divisors of the form 2 2 k 2^2\cdot k . Adding together the exponents of all these divisors, we get m = 1 3 + 2 3 = 9. m=1\cdot 3+2\cdot 3=9.

Jordan Matt
Mar 10, 2018

(1 * 2 * 4 * 5 ... * 100)/2^m = ((25^3) * (5^3))/2^(m-9) Therefore m=9

Thomas Deng
Mar 10, 2018

100 100 can be written as 2 2 × 5 2 2^2\times5^2 . The powers of two can be generated with two cases: 2 × 5 n 2\times5^n or 2 2 × 5 n 2^2\times5^n . The first case has 3 3 powers of 2 because there are 3 3 ways to multiply a power of five by 2, those ways being 5 0 , 5 1 , 5^0,5^1, and 5 2 5^2 . The second case has 2 × 3 = 6 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 2 . Adding these cases up gets us a solution of 3 + 6 = 3+6= 9 .

Akhila F.
Mar 10, 2018

Positive divisors of 100: 1, 2, 4, 5, 10, 20, 25, 50, 100

Product of the positive divisors of 100 = 1 2 4 5 10 20 25 50 100 = 1 0 9 1 \cdot 2 \cdot 4 \cdot 5 \cdot 10 \cdot 20 \cdot 25 \cdot 50 \cdot 100 = 10^9

We know that, 1000 = 1 0 3 = 8 125 = 2 3 5 3 1000 = 10^3 = 8 \cdot 125 = 2^3 \cdot 5^3

Therefore, 1 0 9 = ( 1 0 3 ) 3 = ( 2 3 5 3 ) 3 = 2 9 5 9 10^9 = (10^3)^3 = (2^3 \cdot 5^3)^3 = 2^9 \cdot 5^9

Hence, m = 9 .

Nathan Speer
Mar 9, 2018

Matlab solution: sum(mod(prod(divisors(100)),2.^[1:100])==0)

Harald Brunner
Mar 7, 2018

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
const product = new Array(100) // Empty array for numbers 1..100
    .fill(0) // Fill it so it can be mapped
    .map((e, i) => i + 1) // [1..100]
    .filter(e => 100 % e == 0) // [1,2,4,5,..,100]
    .reduce((acc, x) => acc * x, 1); // Calculate product

/** Infinite sequence of integers. */
function* integers()
{
    let i = 1;
    while (true)
        yield i++;
}

const mValues = [];
for (let m of integers())
{
    const value = Math.pow(2, m);
    // Stop if power exceeds product.
    if (value > product)
        break;

    // Add m to list of potential solutions if the power divides the product.
    if (product % value == 0)
        mValues.push(m);
}
// The last value in the list is the solution.
console.log(mValues[mValues.length - 1]);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def divisors(n): 
    div = [x for x in range(1, n + 1) if n % x == 0]
    return div

def multiply(numbers):  
    total = 1
    for x in numbers:
        total *= x  
    return total  

num = 100
x = multiply(divisors(num))
y = [2**i for i in range(0,50)]

for m, i in enumerate(y):
    if x%i != 0:
        print 'Highest m where the product of all divisors of %d is divisible by 2**m is: %d'  \
            %(num, m-1)
        break

1
Highest m where the product of all divisors of 100 is divisible by 2**m is: 9

Giorgos K.
Feb 26, 2018

Mathematica

Here are the prime factors of the final product

FactorInteger[Times @@ Divisors@100]

{{2, 9}, {5, 9}} which means *2^9 * 5^9 *

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...