How many ordered integer solutions ( a , b , c ) does the equation a b c = 1 0 0 0 have?
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.
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.
Start by looking for positive solutions. There are as many choices for a as there are positive divisors of 1 0 0 0 . For a given choice of a , there are as many choices of b as there are positive divisors of a 1 0 0 0 . Once a , b are chosen, c is fixed. Thus the number of positive integer solutions of this equation is the Dirichlet convolution ( 1 ⋆ σ 0 ) ( 1 0 0 0 ) = a ∣ 1 0 0 0 ∑ σ 0 ( a 1 0 0 0 ) where σ 0 ( n ) is the number of divisors of n . But 1 ⋆ σ 0 is multiplicative, and ( 1 ⋆ σ 0 ) ( p 3 ) = σ 0 ( 1 ) + σ 0 ( p ) + σ 0 ( p 2 ) + σ 0 ( p 3 ) = 1 + 2 + 3 + 4 = 1 0 for any prime p , so that ( 1 ⋆ σ 0 ) ( 1 0 0 0 ) = ( 1 ⋆ σ 0 ) ( 8 ) ( 1 ⋆ σ 0 ) ( 1 2 5 ) = 1 0 2 = 1 0 0 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 negative. Thus there are an additional 3 integer solutions for each positive integer solution, making a total of 4 × 1 0 0 = 4 0 0 solutions.
I loved the observation that the total positive solutions is the sum of number of divisors of each divisor of 1 0 0 0 , which is in fact the dirichlet convolution ( 1 ⋆ σ 0 ) ( 1 0 0 0 ) .
I am thinking how can we use this method if there are four integers a , b , c , d such that a b c d = 1 0 0 0 . Continuing along the same lines, for given a and b , we have as many choices for c as there are positive divisors of a b 1 0 0 0 . Once a , b , c are chosen, d is fixed. How can we evaluate the sum a ∣ 1 0 0 0 ∑ b ∣ a 1 0 0 0 ∑ σ 0 ( a b 1 0 0 0 ) ?
Log in to reply
The key fact is that the constant function 1 is multiplicative, and that Dirichlet convolutions of multiplicative functions are multiplicative. Thus σ 0 = 1 ⋆ 1 is multiplicative, for example. But then 1 ( p j ) ( 1 ⋆ 1 ) ( p j ) = σ 0 ( p j ) ( 1 ⋆ 1 ⋆ 1 ) ( p j ) = ( 1 ⋆ σ 0 ) ( p j ) ( 1 ⋆ 1 ⋆ 1 ⋆ 1 ) ( p j ) = 1 = j + 1 = k = 0 ∑ j σ 0 ( p k ) = 2 1 ( j + 1 ) ( j + 2 ) = k = 0 ∑ j ( 1 ⋆ 1 ⋆ 1 ) ( p k ) = 6 1 ( j + 1 ) ( j + 2 ) ( j + 3 ) and so on, for any prime p and integer j ≥ 0 . Thus ( 1 ⋆ 1 ⋆ 1 ⋆ 1 ) ( 1 0 0 0 ) = ( 1 ⋆ 1 ⋆ 1 ⋆ 1 ) ( 2 3 ) ( 1 ⋆ 1 ⋆ 1 ⋆ 1 ) ( 5 3 ) = 2 0 2 = 4 0 0 and this last is the sum you want.
Log in to reply
Ah yes, thank you :) This makes it clear. For n integers, the equation a 1 a 2 a 3 … a n = 1 0 0 0 would have ( n times 1 ⋆ 1 ⋆ 1 ⋆ ⋯ ⋆ 1 ) ( 1 0 0 0 ) solutions.
( n times 1 ⋆ 1 ⋆ 1 ⋆ ⋯ ⋆ 1 ) ( p j ) is equal to ( n − 1 j + n − 1 ) . We get
( n times 1 ⋆ 1 ⋆ 1 ⋆ ⋯ ⋆ 1 ) ( 1 0 0 0 ) = ( 1 ⋆ 1 ⋆ 1 ⋆ ⋯ ⋆ 1 ) ( 2 3 ) ( 1 ⋆ 1 ⋆ 1 ⋆ ⋯ ⋆ 1 ) ( 5 3 ) = ( n − 1 3 + n − 1 ) 2 = ( 3 n + 2 ) 2
Problem Loading...
Note Loading...
Set Loading...
Since 1 0 0 0 = 2 3 ⋅ 5 3 , each of a , b , c must have the form ± 2 m 5 n for some non-negative integers m , n . As multiplication is commutative and associative, this allows us to break the problem up into three pieces:
Consider just the exponents of 2 first. If A , B , C are the exponents of 2 in a , b , c , respectively then we must have A + B + C = 3 . Since A , B , C are non-negative integers, we can count the number of ways to choose these exponents using "stars-and-bars". This gives ( 2 3 + 2 ) = 1 0 ways to determine the exponents of 2 .
The exponents of 5 are determined in the same way, giving ( 2 3 + 2 ) = 1 0 ways to determine the exponents of 5 .
Then, since the product is positive, there must be an even number of negatives. Therefore, either all are positive ( 1 way) or exactly two are negative ( 3 ways). Therefore, there are 1 + 3 = 4 ways to choose the signs.
Finally, just multiply: ( 2 3 + 2 ) ⋅ ( 2 3 + 2 ) ⋅ 4 = 4 0 0 .