Putnam 2015, Problem A-5

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$.

Solution:
First solution: By inclusion-exclusion, we have
\[
N_q = \sum_{d|q} \mu(d) \left\lfloor \frac{q/d}{4} \right\rfloor = \sum_{d|q} \mu(d) \left\lfloor \frac{q/d}{4} \right\rfloor \equiv \sum_{d|q \text{ squarefree}} \left\lfloor \frac{q/d}{4} \right\rfloor \pmod{2},
\]
where \(\mu\) is the Möbius function. Now
\[
\left\lfloor \frac{q/d}{4} \right\rfloor \equiv \begin{cases} 0 \pmod{2} & \text{if } q/d \equiv 1, 3 \pmod{8} \\ 1 \pmod{2} & \text{if } q/d \equiv 5, 7 \pmod{8}. \end{cases}
\]
So \(N_q\) is odd if and only if \(q\) has an odd number of squarefree factors \(q/d\) congruent to 5 or 7 (mod 8).

If \(q\) has a prime factor \(p\) congruent to 1 or 3 (mod 8), then the squarefree factors \(d\) of \(q\) occur in pairs \(c, pc\), which are either both 1 or 3 (mod 8) or both 5 or 7 (mod 8). Hence \(q\) must have an even number of factors that are congruent to 5 or 7 (mod 8), and so \(N_q\) is even in this case.

If \(q\) has two prime factors \(p_1\) and \(p_2\), each congruent to either 5 or 7 (mod 8), then the squarefree factors \(d\) of \(q\) occur in quadruples \(d, p_1d, q_1d, p_1q_1d\), which are then congruent respectively to some permutation of 1, 3, 5, 7 (mod 8) (if \(p_1\) and \(p_2\) are distinct mod 8) or are congruent respectively to \(d, p_1d, p_1d, d\) (mod 8). Either way, we see that exactly two of the four residues are congruent to 5 or 7 (mod 8). Thus again \(q\) must have an even number of factors that are 5 or 7 (mod 8), and so \(N_q\) is even in this case as well.

If \(q = 1\), then \(N_q = 0\) is even. The only case that remains is that \(q = p^k\) is a positive power of a prime \(p\) congruent to 5 or 7 (mod 8). In this case, \(q\) has two squarefree factors, 1 and \(p\), of which exactly one is congruent to 5 or 7 (mod 8). We conclude that \(N_q\) is odd in this case, as desired.

Second solution: Consider the set \(S\) of all integers in \(\{1, \ldots, q-1\}\) that are even and relatively prime to \(q\). Then the product of all elements in \(S\) is
\[
2^{\phi(q)/2} \prod_{\substack{1 \leq a \leq (q-1)/2 \\ (a,q)=1}} a.
\]
On the other hand, we can rewrite the set of elements in \(S\) (mod \(q\)) as a set \(T\) of residues in the interval \([-(q-1)/2, (q-1)/2]\). Then for each \(1 \leq a \leq (q-1)/2\) with \((a,q) = 1\), \(T\) contains exactly one element from \(\{a, -a\}\): if \(-2r \equiv 2s \pmod{q}\) for some \(r, s \in \{1, \ldots, (q-1)/2\}\), then \(r \equiv -s \pmod{q}\), which is impossible given the ranges of \(r\) and \(s\). Thus the product of all elements in \(T\) is
\[
(-1)^n \prod_{\substack{1 \leq a \leq (q-1)/2 \\ (a,q)=1}} a,
\]
where \(n\) denotes the number of elements of \(S\) greater than \((q-1)/2\). We conclude that \((-1)^n \equiv 2^{\phi(q)/2} \pmod{q}\).

However, note that the number of elements of \(S\) less than \((q-1)/2\) is equal to \(N_q\), since dividing these numbers by 2 gives exactly the numbers counted by \(N_q\). Hence the total cardinality of \(S\) is \(N_q + n\); however, this cardinality also equals \(\phi(q)/2\) because the numbers in \(\{1, \ldots, q-1\}\) relatively prime to \(q\) come in pairs \(\{a, q-a\}\) in each of which exactly one member is even. We thus obtain
\[
(-1)^{N_q} = (-1)^{\phi(q)/2 + n} \equiv (-1)^{\phi(q)/2} 2^{\phi(q)/2} = (-2)^{\phi(q)/2} \pmod{q}.
\]
If \(q = 1\), then \(N_q\) is even. If \(q\) has more than one prime factor, then the group \((\mathbb{Z}/q\mathbb{Z})^\times\) has exponent dividing \(\phi(q)/2\), so \((-1)^{N_q} \equiv (-2)^{\phi(q)/2} \equiv 1 \pmod{q}\), and thus \(N_q\) must be even in this case as well. Finally, suppose that \(q\) is a prime power \(p^k\) with \(p\) odd and \(k\) positive. Since \((\mathbb{Z}/q\mathbb{Z})^\times\) is a cyclic group of order \(\phi(q) = p^{k-1}(p-1)\), in which the only square roots of unity are \(\pm 1\), it follows that \((-2)^{\phi(q)/2} \equiv \pm 1 \pmod{q}\) in accordance with whether \((-2)^{(p-1)/2} \equiv \pm 1 \pmod{p}\), i.e., whether \(-2\) is a quadratic residue or non-residue. But recall that \(-2\) is a quadratic residue modulo \(p\) if and only if \(p \equiv 1, 3 \pmod{8}\). Thus \(N_q\) is odd in this case if and only if \(p \equiv 5\) or \(7 \pmod{8}\).

We conclude that for any odd integer \(q \geq 1\), the quantity \(N_q\) is odd if and only if \(q = p^k\) with \(k\) positive and \(p\) a prime that is 5 or 7 (mod 8).

Remark: The combination of the two solutions recovers Gauss's criterion for when \(-2\) is a quadratic residue modulo \(p\), with essentially the original proof.