We define $$S(n)=\sum_{a=2+(n\pmod 2)}^{n-2} \sharp(\{j,1\leq j<n \pmod{a},(a,j)=1\})\ .$$
(Searching the OEIS yielded no results.)
For $n>2$ we have the following experimental observations (checked up to $n=1000$) on $S(n)\pmod 4$:
For $n>2$ the number $S(n)$ seems to be even for $n\equiv -1,0\pmod 4$ and odd for $n\equiv 1,2\pmod 4$.
We have seemingly the following congruences modulo $4$:
$S(n)\equiv 0\pmod 4$ for all $n\equiv 0\pmod 8$.
If $n\equiv 1\pmod 8$ then $S(n)\equiv 1\pmod 4$ if and only if $n=p^{2e}$ is a prime-power (of necessarily even exponent) for some prime $p\equiv 3\pmod 4$ and $S(n)\equiv 3\pmod 4$ otherwise (i.e. if $n\equiv 1\pmod 8$ is not a prime power of a prime $\equiv 3\pmod 4$).
If $n\equiv 2\pmod 8$ then $S(n)\equiv 3\pmod 4$ if and only if $n=2p^{2e}$ is twice a prime-power (of necessarily even exponent) for some prime $p\equiv 3\pmod 4$ and $S(n)\equiv 1\pmod 4$ otherwise (i.e. if $n\equiv 2\pmod 8$ is not twice a prime power of a prime $\equiv 3\pmod 4$).
If $n\equiv 3\pmod 8$ then $S(n)\equiv 0\pmod 4$ if and only if $n=p^{2e+1}$ is a prime-power (necessarily of odd exponent $2e+1$) of a prime $p\equiv 3\pmod 8$ and $S(n)\equiv 2$ otherwise.
If $n\equiv 4\pmod 8$ and $n\geq 12$ then $S(n)\equiv 2\pmod 8$.
If $n\equiv 5\pmod 8$ then $S(n)\equiv 1\pmod 4$.
If $n\equiv 6\pmod 8$ then $S(n)\equiv 1\pmod 4$ if and only if $n=2p^{2e+1}$ for some prime $p\equiv 3\pmod 4$ and $S(n)\equiv 3\pmod 4$ otherwise.
If $n\equiv 7\pmod 8$ then $S(n)\equiv 2\pmod 4$ if and only if $n=p^{2e+1}$ is a prime-power (necessarily of odd exponent $2e+1$) of an odd prime $p\equiv 7\pmod 8$ and $S(n)\equiv 0\pmod 7$ otherwise.
Is there an explanation (or counterexample) for these congruences?
