Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

counting and probability senior

Problem

How many subsets of the set of divisors of contain only composite numbers? For example, and are two such sets. Include the empty set in your count.
Solution
We know that the number of subsets of any given set is equal to where is the number of elements in the set. First, then, we need to find the number of composite divisors. The prime factorization of is so there are total divisors. (To see this, note that we can form a divisor of the form by freely choosing and ). Of these, is neither prime nor composite, and and are prime, for a total of composite divisors. Therefore there are subsets of the divisors of with only composite divisors.
Final answer
512