Pair me up

Solution 1: Consider the 900 pairs of $(a,b)$ with both less than or equal to 30. Since $\frac {1}{2}$ of them have $a$ even, $\frac {1}{2}$ of them have $b$ even, so $1 - (1-\frac {1}{2})^2 = \frac {3}{4}$ of them will have $ab$ not even. Similarily, $1 - (1-\frac {1}{3})^2 = \frac {8}{9}$ of them will have $ab$ not a multiple of 3, $1- (1-\frac {1}{5})^2 = \frac {24}{25}$ of them will have $ab$ not a multiple of 5. These events are independent of each other, so $\frac {3}{4} \times \frac {8}{9} \times \frac {24}{25}$ of these pairs will satisfy our conditions. Thus, there are $900 \times \frac {3}{4} \times \frac {8}{9} \times \frac {24}{25} = 576$ ordered pairs satisfying the condition.

Solution 2: This is similar to Euler's Totient Function, and we can proceed similarly, to show that the general form is $N^2 \prod \left(1-\frac {1}{p_k^2}\right)$ .

Note: This is known as Jordan's Totient Function, of which Euler's function is a special case.