Triplets divisors of 1000

How many ordered integer solutions ( a , b , c ) (a,b,c) does the equation a b c = 1000 abc = 1000 have?


The answer is 400.

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.

2 solutions

Brian Moehring
Feb 8, 2017

Since 1000 = 2 3 5 3 1000 = 2^3\cdot 5^3 , each of a , b , c a,b,c must have the form ± 2 m 5 n \pm 2^m5^n for some non-negative integers m , n m,n . As multiplication is commutative and associative, this allows us to break the problem up into three pieces:

  • Count the number of ways we can choose the exponents of 2 2 .
  • Count the number of ways we can choose the exponents of 5 5 .
  • Count the number of ways we can choose the signs.

Consider just the exponents of 2 2 first. If A , B , C A,B,C are the exponents of 2 2 in a , b , c a,b,c , respectively then we must have A + B + C = 3 A+B+C = 3 . Since A , B , C A,B,C are non-negative integers, we can count the number of ways to choose these exponents using "stars-and-bars". This gives ( 3 + 2 2 ) = 10 \binom{3+2}{2} = 10 ways to determine the exponents of 2 2 .

The exponents of 5 5 are determined in the same way, giving ( 3 + 2 2 ) = 10 \binom{3+2}{2} = 10 ways to determine the exponents of 5 5 .

Then, since the product is positive, there must be an even number of negatives. Therefore, either all are positive ( 1 1 way) or exactly two are negative ( 3 3 ways). Therefore, there are 1 + 3 = 4 1+3 = 4 ways to choose the signs.

Finally, just multiply: ( 3 + 2 2 ) ( 3 + 2 2 ) 4 = 400 . \binom{3+2}{2} \cdot \binom{3+2}{2} \cdot 4 = \boxed{400}.

Well presented! I loved how you broke up the complex problem into three simple parts of distributing the powers of 2, 5 and the signs, and then used the rule of product to get the final result.

Pranshu Gaba - 4 years, 3 months ago
Mark Hennings
Feb 7, 2017

Start by looking for positive solutions. There are as many choices for a a as there are positive divisors of 1000 1000 . For a given choice of a a , there are as many choices of b b as there are positive divisors of 1000 a \tfrac{1000}{a} . Once a , b a,b are chosen, c c is fixed. Thus the number of positive integer solutions of this equation is the Dirichlet convolution ( 1 σ 0 ) ( 1000 ) = a 1000 σ 0 ( 1000 a ) (1 \star \sigma_0)(1000) \; = \; \sum_{a|1000} \sigma_0\big(\tfrac{1000}{a}\big) where σ 0 ( n ) \sigma_0(n) is the number of divisors of n n . But 1 σ 0 1 \star \sigma_0 is multiplicative, and ( 1 σ 0 ) ( p 3 ) = σ 0 ( 1 ) + σ 0 ( p ) + σ 0 ( p 2 ) + σ 0 ( p 3 ) = 1 + 2 + 3 + 4 = 10 (1 \star \sigma_0)(p^3) \; = \; \sigma_0(1) + \sigma_0(p) + \sigma_0(p^2) + \sigma_0(p^3) \; =\; 1 + 2 + 3 + 4 \; = \; 10 for any prime p p , so that ( 1 σ 0 ) ( 1000 ) = ( 1 σ 0 ) ( 8 ) ( 1 σ 0 ) ( 125 ) = 1 0 2 = 100 (1 \star \sigma_0)(1000) \; = \; (1 \star \sigma_0)(8) (1 \star \sigma_0)(125) \; = \; 10^2 \; = \; 100 Now we have the positive integer solutions, we find all solutions by noting that any positive integer solution could be converted into an integer solution by making any two of the three numbers a , b , c a,b,c negative. Thus there are an additional 3 3 integer solutions for each positive integer solution, making a total of 4 × 100 = 400 4 \times 100 = \boxed{400} solutions.

I loved the observation that the total positive solutions is the sum of number of divisors of each divisor of 1000 1000 , which is in fact the dirichlet convolution ( 1 σ 0 ) ( 1000 ) (1 \star \sigma_0) (1000) .

I am thinking how can we use this method if there are four integers a , b , c , d a, b, c, d such that a b c d = 1000 abcd = 1000 . Continuing along the same lines, for given a a and b b , we have as many choices for c c as there are positive divisors of 1000 a b \frac{1000}{ab} . Once a , b , c a, b, c are chosen, d d is fixed. How can we evaluate the sum a 1000 b 1000 a σ 0 ( 1000 a b ) \displaystyle\sum_{a|1000} \sum_{b|\frac{1000}{a}} \sigma_0\big(\tfrac{1000}{ab}\big) ?

Pranshu Gaba - 4 years, 3 months ago

Log in to reply

The key fact is that the constant function 1 1 is multiplicative, and that Dirichlet convolutions of multiplicative functions are multiplicative. Thus σ 0 = 1 1 \sigma_0 = 1 \star 1 is multiplicative, for example. But then 1 ( p j ) = 1 ( 1 1 ) ( p j ) = σ 0 ( p j ) = j + 1 ( 1 1 1 ) ( p j ) = ( 1 σ 0 ) ( p j ) = k = 0 j σ 0 ( p k ) = 1 2 ( j + 1 ) ( j + 2 ) ( 1 1 1 1 ) ( p j ) = k = 0 j ( 1 1 1 ) ( p k ) = 1 6 ( j + 1 ) ( j + 2 ) ( j + 3 ) \begin{aligned} 1(p^j) & = 1 \\ (1 \star 1)(p^j) \; =\; \sigma_0(p^j) & = j+1 \\ (1 \star 1 \star 1)(p^j) \; = \; (1 \star \sigma_0)(p^j) & = \sum_{k=0}^j \sigma_0(p^k) \; = \; \tfrac12(j+1)(j+2) \\ (1 \star 1 \star 1 \star 1)(p^j) & = \; \sum_{k=0}^j (1 \star 1 \star 1)(p^k) \; =\; \tfrac16(j+1)(j+2)(j+3) \end{aligned} and so on, for any prime p p and integer j 0 j \ge 0 . Thus ( 1 1 1 1 ) ( 1000 ) = ( 1 1 1 1 ) ( 2 3 ) ( 1 1 1 1 ) ( 5 3 ) = 2 0 2 = 400 (1 \star 1 \star 1 \star 1)(1000) \; = \; (1 \star 1 \star 1 \star 1)(2^3) (1 \star 1 \star 1 \star 1)(5^3) \; = \; 20^2 \; = \; 400 and this last is the sum you want.

Mark Hennings - 4 years, 3 months ago

Log in to reply

Ah yes, thank you :) This makes it clear. For n n integers, the equation a 1 a 2 a 3 a n = 1000 a_1 a_2 a_3 \ldots a_n = 1000 would have ( 1 1 1 1 n times ) ( 1000 ) (\underbrace{1 \star 1 \star 1 \star \cdots \star 1}_{n \text{ times}}) (1000) solutions.

( 1 1 1 1 n times ) ( p j ) (\underbrace{1 \star 1 \star 1 \star \cdots \star 1}_{n \text{ times}}) (p^j) is equal to ( j + n 1 n 1 ) \binom{j + n-1}{n -1} . We get

( 1 1 1 1 n times ) ( 1000 ) = ( 1 1 1 1 ) ( 2 3 ) ( 1 1 1 1 ) ( 5 3 ) = ( 3 + n 1 n 1 ) 2 = ( n + 2 3 ) 2 \begin{aligned} (\underbrace{1 \star 1 \star 1 \star \cdots \star 1}_{n \text{ times}}) (1000) &= (1 \star 1 \star 1 \star \cdots \star 1) (2^3) (1 \star 1 \star 1 \star \cdots \star 1) (5^3) \\ & = \binom{3 + n - 1}{n - 1}^2 \\ & = \binom{ n + 2}{3}^2 \end{aligned}

Pranshu Gaba - 4 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...