Question 62
Let $n$ be a positive integer, and let $A_n$, respectively $B_n$, be the set of non-negative integers $k \lt n$ such that the number of distinct prime factors of $\gcd(k, n)$ is even, respectively odd. Show that $|A_n| = |B_n|$ if $n$ is even, and $|A_n| \gt |B_n|$ if $n$ is odd.