NMO Selection Tests for BMO and IMO

Since $\gcd(k, n)$ depends only upon the residue class of $k$ modulo $n$, $|A_n| - |B_n| = \sum_k (-1)^{s(k,n)}$, where $s(k, n)$ is the number of distinct prime factors of $\gcd(k, n)$, and $k$ ranges over any complete residue system modulo $n$.
We shall prove that the above sum equals $n \prod_{p|n} (1 - 2/p)$, $p$ prime, whence the conclusion; the latter is precisely the number of positive integers $k < n$ such that $k$ and $k+1$ are both coprime to $n$.
In the above notation, let $e(k, n) = (-1)^{s(k,n)}$ and let $f(n) = \sum_k e(k, n)$. We show that $f$ is a numerical multiplicative function — that is, if $n_1$ and $n_2$ are coprime positive integers, then $f(n_1n_2) = f(n_1)f(n_2)$.
If $n_1, n_2$ are coprime positive integers, then $e(k, n_1n_2) = e(k, n_1)e(k, n_2)$. Further, if $k_i$ ranges once over a complete residue system modulo $n_i$, $i = 1, 2$, then $k = k_1n_2 + k_2n_1$ ranges once over a complete residue system modulo $n_1n_2$, and $e(k, n_i) = e(k_i, n_i)$, $i = 1, 2$. Hence $e(k, n_1n_2) = e(k, n_1)e(k, n_2) = e(k_1, n_1)e(k_2, n_2)$, and
$$f(n_1n_2) = \sum_k e(k, n_1n_2) = \sum_{k_1} \sum_{k_2} e(k_1, n_1)e(k_2, n_2) = f(n_1)f(n_2).$$
Finally, if $p$ is a prime, and $m$ is a positive integer, then $f(p^m)$ equals the number of $k$'s coprime to $p$, which is $p^m - p^{m-1}$, minus the number of $k$'s divisible by $p$, which is $p^{m-1}$, so $f(p^m) = p^m(1 - 2/p)$. This ends the proof.