2015 Putnam A5

Let $q$ be an odd positive integer, and let $N_q$ denote the number of integers $a$ such that $0 < a < q/4$ and $\gcd(a,q) = 1$. Show that $N_q$ is odd if and only if $q$ is of the form $p^k$ with $k$ a positive integer and $p$ a prime congruent to $5$ or $7$ modulo $8$.

令 $q$ 为奇数正整数，并令 $N_q$ 表示满足 $0 < a < q/4$ 且 $\gcd(a,q) = 1$ 的整数 $a$ 的数量。证明 $N_q$ 是奇数当且仅当 $q$ 的形式为 $p^k$，其中 $k$ 是正整数，$p$ 是与 $5$ 或 $7$ 模 $8$ 同余的素数。