A set of positive integers satisfies the property that when 10^{20} , 15^{10} and 24^{15} are divided by any number in this set, at least one of the remainders is zero. What is the total number of elements in this set?
P.S. Found the problem somewhere, don't know the exact correct answer. Solutions are always welcome..:D
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.
From the way the set is defined it's clearly that any element should be a divisor of at least one of the three numbers.
If A = D 1 0 2 0 , B = D 1 5 1 0 , C = D 2 4 2 0 we need to calculate ∣ A ∪ B ∪ C ∣ .
We should know that if n = p 1 k 1 p 2 k 2 . . . p m k m is a prime factorization of n (when n > 1 ), then the number of divisors of n is:
∣ D n ∣ = ( 1 + k 1 ) ( 1 + k 2 ) . . . ( 1 + k m )
(eg. If n = 6 0 = 2 2 3 1 5 1 then 60 should have D 6 0 = ( 1 + 2 ) ( 1 + 1 ) ( 1 + 1 ) = 1 2 divisors, which is true because D 6 0 = { 1 , 2 , 3 , 4 , 5 , 6 , 1 0 , 1 2 , 1 5 , 2 0 , 3 0 , 6 0 } )
The principal of inclusion and exclusion says that
∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − ∣ A ∩ B ∣ − ∣ A ∩ C ∣ − ∣ B ∩ C ∣ + ∣ A ∩ B ∩ C ∣
1 0 2 0 = 2 2 0 5 2 0 then ∣ A ∣ = ( 1 + 2 0 ) ( 1 + 2 0 ) = 4 4 1
1 5 1 0 = 3 1 0 5 1 0 then ∣ B ∣ = ( 1 + 1 0 ) ( 1 + 1 0 ) = 1 2 1
2 5 1 5 = 2 4 5 3 1 5 then ∣ A ∣ = ( 1 + 4 5 ) ( 1 + 1 5 ) = 7 3 6
∣ A ∩ B ∣ = D 5 1 0 = 1 + 1 0 = 1 1
∣ A ∩ C ∣ = D 2 2 0 = 1 + 2 0 = 2 1
∣ B ∩ C ∣ = D 3 1 0 = 1 + 1 0 = 1 1
∣ A ∩ B c a p C ∣ = D 1 = 1
Plug everything in the formula of ∣ A ∪ B ∪ C ∣ .