= Solution
The <inclusion-exclusion principle> states that for finite sets $A_1,\ldots,A_k$,
$$
\left|\bigcup_iA_i\right|
=\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|+\cdots+(-1)^{k+1}|A_1\cap\cdots\cap A_k|.
$$
For each prime $p\mid n$, exclude pairs whose two coordinates are divisible by $p$. For a set of distinct prime divisors $p_1,\ldots,p_j$, exactly $n^2/(p_1\cdots p_j)^2$ pairs have both coordinates divisible by their product. Inclusion-exclusion therefore gives
$$
\boxed{|Y|=n^2\prod_{p\mid n}\left(1-\frac1{p^2}\right)}.
$$
Back to article page
