RO-TST 2014 Problem 13

Let $n$ be a positive integer and let $A_n$ respectively $B_n$ be the set of nonnegative integers $k<n$ such that the number of distinct prime factors of $\gcd(n,k)$ is even (respectively odd). Show that $|A_n|=|B_n|$ if $n$ is even and $|A_n|>|B_n|$ if $n$ is odd.

Example: $A_{10} = \left\{ 0,1,3,7,9 \right\}$ , $B_{10} = \left\{ 2,4,5,6,8 \right\}$ .