Let $q = p_1^{e_1} p_2^{e_2} \dots p_n^{e_n}$. By Principle of Inclusion-Exclusion (or Moebius inversion?) we have \[ N_q = \sum_{S \subset \{1, \dots, n\}} (-1)^{|S|} \left\lfloor \frac{q}{4\prod_{s \in S} p_s} \right\rfloor . \]The $(-1)^{|S|}$ vanishes when taking modulo $2$. Now, $\left\lfloor \frac{\bullet}{4} \right\rfloor \pmod 2$ depends only on the input modulo $8$, equalling $0$ for $1,3 \pmod 8$ and $1$ for $5,7\pmod8$. As $p^2 \equiv 1 \pmod 8$ the exponents in the floor also can be taken mod $2$. Therefore, we can simplify this to \[ N_q \equiv \sum_{S \subset \{1, \dots, n\}} \left\lfloor \frac{q\prod_{s \in S} p_s}{8} \right\rfloor \pmod 2. \]Let $A(S) = \left\lfloor \frac{q\prod_{s \in S} p_s}{8} \right\rfloor \pmod 2$. The solution now proceeds in three cases. If any prime is $1$ or $3$ mod $8$, say $p_1$, then $A(T) = A(T \cup \{1\})$ for $T \subset \{2, \dots, n\}$ and thus $N_q$ is even. If all primes are $5$ or $7$ mod $8$ and $n \ge 2$, then $A(T) = A(T \cup \{1,2\})$ and $A(T \cup \{1\}) = A(T \cup \{2\})$ for $T \subset \{3, \dots, n\}$ and thus $N_q$ is even. But if $n = 1$ and $p_1 \equiv 5,7 \pmod 8$ then $A(\varnothing) + A(\{1\})$ is always odd. This completes the proof.

v_Enhance wrote: Let $q = p_1^{e_1} p_2^{e_2} \dots p_n^{e_n}$. By Principle of Inclusion-Exclusion (or Moebius inversion?) we have \[ N_q = \sum_{S \subset \{1, \dots, n\}} (-1)^{|S|} \left\lfloor \frac{q}{4\prod_{s \in S} p_s} \right\rfloor . \] Alternatively, after you've found that \[ N_q = \sum_{S \subset \{1, \dots, n\}} (-1)^{|S|} \left\lfloor \frac{q}{4\prod_{s \in S} p_s} \right\rfloor \]you could have saved a lot of work by noting that, for every pair of odd integers $m,n$, we have \[ \Big\lfloor \frac{m}{4} \Big\rfloor + \Big\lfloor \frac{n}{4} \Big\rfloor \equiv \Big\lfloor \frac{mn}{4} \Big\rfloor \text{ (mod } 2 \text{)}. \]From this observation, it is immediate that \[ N_q \equiv \Big\lfloor \frac{(p_1^{2e_1-1} p_2^{2e_2-1} \dots p_n^{2e_n-1})^{2^{n-1}}}{4} \Big\rfloor. \]If $n=1$, then $N_q$ is odd if and only if $p_1$ is $5$ or $7$ (mod $8$). If $n \ge 2$, then it is clear that $N_q$ is even, because $(p_1^{2e_1-1} p_2^{2e_2-1} \dots p_n^{2e_n-1})^{2^{n-1}}$ is a square.

Another solution based on Gauss Lemma: Let $1,2,\ldots,\frac{q-1}{2}$ be numbers coprime to $q$ less than $q/2$. We multiply each number on the list by $-2$ and get list of some $\varphi(q)/2$ numbers. Let us observe that for every $x$ exactly one number from the pair $(x,q-x)$ is on the list. Moreover $-2x \in (q/2,q)$ implies $x \in (0,q/4)$ thus we get $$ (-2)^{\varphi(q)/2} \left(1 \cdot 2 \cdot \ldots \cdot \frac{q-1}{2}\right) = (-1)^{N_q} \left(1 \cdot 2 \cdot \ldots \cdot \frac{q-1}{2}\right) \pmod q$$And so $(-2)^{\varphi(q)/2} \equiv -1 \pmod q$. If $q$ has at least two distinct odd prime factors then of course $a^{\varphi(q)/2} = 1 \pmod q$, for every $(a,q)=1$. If $q=p^k$ then our condition is equivalent to $\left(\frac{-2}{p}\right)=-1$ so $p \equiv 5,7 \pmod 8$.

Here's a simple generalization. The proof is virtually identical to v_Enhance's proof. Let $j$ be a positive integer. Let $q$ be an odd positive integer, and let $N_q$ denote the number of integers $a$ such that $0<a<q/2^j$ 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 $2^j+1,2^j+3,\ldots,2^{j+1}-1$ modulo $2^{j+1}.$

@OP $N_q$ is odd and only if $P$ =$1$ with $P_5$ or $P_7$ nonempty.

DIffCALCFTW wrote: @OP $N_q$ is odd and only if $P$ =$1$ with $P_5$ or $P_7$ nonempty. @DIffCALCFTW I guess that is true. But I can't write up a full proof of number theory, plus my level of mathematics is not that high. @OP ask @DIffCALCFTW to write up a proof for you.

@CantonMathGuy What are you trying to prove? I suck at math compared to you.

We can actually derive a pretty explicit formula for $N_q$. Let $q=p_1^{e_1}\cdots p_r^{e_r}$. By a standard inclusion-exclusion argument, we obtain \[N_q=\sum_{g_1,\ldots,g_r\in\{0,1\}}\left\lfloor\frac{q/4}{\prod_{i=1}^r p_i^{g_i}}\right\rfloor.\]We see that this rewrites as \[N_q=\frac{\phi(q)}{4}-\sum_{g_1,\ldots,g_r\in\{0,1\}}\left\{\frac{q/4}{\prod_{i=1}^r p_i^{g_i}}\right\}.\]Note that if $v$ is odd, then $\{v/4\}=1$ if $v\equiv 1\pmod{4}$, and $\{v/4\}=3$ if $v\equiv 3\pmod{4}$. To this end, suppose $m$ of the $p_i$ are $1\pmod{4}$, and suppose $n$ of them are $3\pmod{4}$. Note that $m+n=r$. There are $\binom{n}{\ell}\binom{m}{k-\ell}$ choices of the $g_i$ where $k$ is the number of nonzero $g_i$, and $\ell$ is the number of them that correspond to a $3\pmod{4}$ prime. Using the just defined variables, we see that \[\left\{\frac{q/4}{\prod_{i=1}^r p_i^{g_i}}\right\}=2+(-1)^\ell(-1)^{\frac{q-1}{4}},\]so \begin{align*}N_q&=\frac{\phi(q)}{4}-\frac{1}{4}\sum_{k=0}^r(-1)^k\sum_{\ell=0}^k\binom{n}{\ell}\binom{m}{k-\ell}\left(2+(-1)^\ell(-1)^{\frac{q-1}{4}}\right)\\ &= \frac{\phi(q)}{4}-\frac{(-1)^{\frac{q-1}{4}}}{4}\sum_{k=0}^r(-1)^k\sum_{\ell=0}^k\binom{n}{\ell}\binom{m}{k-\ell}(-1)^\ell \end{align*}where the last equality follows from Vandermonde's identity, and then the fact that $\sum_{k=0}^r(-1)^k\binom{r}{k}=0$. It's easy to see that \[\sum_{\ell=0}^k\binom{n}{\ell}\binom{m}{k-\ell}(-1)^\ell=[x^k]((1-x)^n(1+x)^m)=:[x^k]P(x)\]where $[x^k]P(x)$ is the $x^k$ coefficient of $P(x)=(1-x)^n(1+x)^m$. Therefore, \[N_q=\frac{\phi(q)}{4}-\frac{(-1)^{\frac{q-1}{4}}}{4}P(-1).\]We now split into cases. Case 1: $q$ has a prime factor that is $1\pmod{4}$. In this case, we see that $m\ge 1$, so $P(-1)=0$, so \[N_q=\frac{\phi(q)}{4}.\]Suppose $p\equiv 1\pmod{4}$ divides $q$, and let $q=p^kj$ where $p\nmid j$. Then, \[N_q=\frac{p-1}{4}p^{k-1}\phi(\ell).\]If $\ell\ne 1$, then $\phi(\ell)$ is even, so we automatically have $N_q$ even. Thus, $q=p^k$. But we also need $\frac{p-1}{4}$ to be odd, so in this case, $q=p^k$ where $p\equiv 5\pmod{8}$. It is easy to see that this does in fact give odd $N_q$. Case 2: All of the prime factors of $q$ are $3\pmod{4}$. In this case, we see $P(-1)=2^r$. So if $r\ge 3$ we see that $N_q\equiv \frac{\phi(q)}{4}\pmod{2}$. But \[\frac{\phi(q)}{4}=\frac{(p_1-1)\cdots(p_r-1)}{4}p_1^{e_1-1}\cdots p_r^{e_r-1},\]which is even. If $r=2$, then we get \[\frac{1}{4}(p_1-1)(p_2-1)p_1^{e_1-1}p_2^{e_2-1}+(-1)^{q/4}\equiv 1+1\equiv 0\pmod{2},\]so it's even. Thus, we must have $r=1$, so $q=p^k$ where $p\equiv 3\pmod{4}$. In this case, we compute \[N_q=\frac{1}{4}\left((p-1)p^{k-1}+2(-1)^k\right).\]It is straightforward to check that this is always even for $p\equiv 3\pmod{8}$, and always odd for $p\equiv 7\pmod{8}$. Therefore, in this case, $q=p^k$ for $p\equiv 7\pmod{8}$, and it's easy to see that $N_q$ is odd in this case. Thus, we have shown that $N_q$ is odd if and only if $q=p^k$ for some prime $p\equiv 5,7\pmod{8}$. $\blacksquare$

_el_doopa wrote: Another solution based on Gauss Lemma: Let $1,2,\ldots,\frac{q-1}{2}$ be numbers coprime to $q$ less than $q/2$. We multiply each number on the list by $-2$ and get list of some $\varphi(q)/2$ numbers. Let us observe that for every $x$ exactly one number from the pair $(x,q-x)$ is on the list. Moreover $-2x \in (q/2,q)$ implies $x \in (0,q/4)$ thus we get $$ (-2)^{\varphi(q)/2} \left(1 \cdot 2 \cdot \ldots \cdot \frac{q-1}{2}\right) = (-1)^{N_q} \left(1 \cdot 2 \cdot \ldots \cdot \frac{q-1}{2}\right) \pmod q$$And so $(-2)^{\varphi(q)/2} \equiv -1 \pmod q$. If $q$ has at least two distinct odd prime factors then of course $a^{\varphi(q)/2} = 1 \pmod q$, for every $(a,q)=1$. If $q=p^k$ then our condition is equivalent to $\left(\frac{-2}{p}\right)=-1$ so $p \equiv 5,7 \pmod 8$. I don't understand this line: Let $1,2,\ldots,\frac{q-1}{2}$ be numbers coprime to $q$ less than $q/2$. How do you know that there are exactly $\frac{q-1}{2}$ numbers coprime to $q$ less than $q/2$.? Secondly it is not necessary that all numbers in the list $1,2,3,\ldots, \frac{q-1}{2}$ are coprime to $q$.

Not bad: I think it is useful to take the problem one prime at a time. The question is pointless for $q\le 4$, so take $q\ge 5$. Suppose $q$ does have $N_q$ odd. Let $p\mid q$ and $\nu_p(q)=k$. Let $q/p^k = r$. Suppose for now that $r>1$. Then the number of integers $0<s<q/4=rp^k/4$ relatively prime to $r$ is congruent to $N_r$ modulo $2$ because if $p^k\equiv 1\pmod 4$ we count $N_s$ along with $\phi(r)(p^k-1)/4$ numbers and if $p^k\equiv 3\pmod 4$ we count $N_s$ less than $\phi(r)(p^k+1)/4$ numbers. But there are also $N_r$ integers $0<ps<q/4 = rp^k/4$ by a similar argument because then we count solutions to $0<s<rp^{k-1}/4$. So we count $N_r-N_r=0$ modulo $2$ choices of $0<s<q/4=rp^k/4$ with $\gcd(s,rp^k)=1$ in this case. Then $q$ must be a prime power $p^k$. In this case, we count $\lfloor p^k/4\rfloor - \lfloor p^{k-1}/4\rfloor$ total $0<n<q/4$ with $\gcd(n,q)=1$ by a similar argument. Modulo $8$, either both of $p^k$ and $p^{k-1}$ reduce to a residue $0\le r<8$ with $0\le r<3$ or exactly one does. The latter case yields odd $N_q$ and occurs for $p\equiv 5,7\pmod 8$ as desired.