, 2010

Consider the set $\mathcal{A}$ of all (ordered) pairs $(X, Y)$ with $X, Y \subseteq T$ and $\gcd(x, y) = 1$ for all $x \in X$ and $y \in Y$. Clearly $X$ and $Y$ are disjoint for any $(X, Y) \in \mathcal{A}$. We have the following claims.

i. If $X'$ is good, then the number of pairs $(X', Y) \in \mathcal{A}$ is odd: In fact, in this case the only such pair in $\mathcal{A}$ is $(X', \emptyset)$.

ii. If $X'$ is not good, then the number of pairs $(X', Y) \in \mathcal{A}$ is even: Let $Z \subseteq T \setminus X'$ contain the numbers that are relatively prime to all numbers in $X'$. Because $X'$ is not good, $Z$ is non-empty. Now, note that $(X', Y) \in \mathcal{A}$ if and only if $Y \subseteq Z$, hence the number of choices for $Y$ is a power of $2$.

Finally, note that $(\emptyset, \emptyset)$ is the only element of $\mathcal{A}$ of the form $(X, X)$, hence $(X, Y) \mapsto (Y, X)$ groups the elements of $\mathcal{A} \setminus \{(\emptyset, \emptyset)\}$ into pairs. Thus, $\mathcal{A}$ has an odd number of elements. By (i) and (ii), this implies that the number of good subsets is odd, completing the proof.