The integers in the set $\{1,2, \ldots, 20\}$ will be painted with two colors, white and black, such that both colors are used. Additionally, the product of the numbers of one color should not have any common prime factors with the product of the numbers of the other color. In how many ways can this be done?
Solution

Regardless of the colors chosen for the other numbers, we have two options for the color of the number 1. We also have two options for the color of the number $2$, and once it has been chosen, all numbers in the set $\{4,6,8,10,12,14,16,18,20\}$ must have the same color as the number 2. Since there are numbers in this set that share prime factors with the numbers in the set $\{3,7,9,15\}$, these 4 odd numbers must also have the color of the number 2. It remains to choose the color of the numbers in the set $\{11,13,17,19\}$, and each of these can be chosen independently, as there are no other numbers in the initial set with the same prime factors. Thus, the total number of colorings is $2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2=2^{6}$.