Divisors $1\bmod 4$ more than $3\bmod 4$ For any positive integer $n$, let $f(n)$ denote the number of positive divisors of $n$ which are $1\bmod 4$, and $g(n)$ denote the number of positive divisors of $n$ which are $3\bmod 4$. Is it true that $f(n)\geq g(n)$ always? It seems to be true for $n$ at least up to $50$.
 A: Hint: Let $D_1(n)$ be the number of divisors of $n$ of the form $4k+1$, and let $D_3(n)$ be the number of divisors of $n$ of the form $4k+3$. Show that $D_1(n)-D_3(n)$ is a multiplicative function.
Calculation of $D_1(n)-D_3(n)$ for prime powers is easy.
Remark: A nice theorem of Jacobi shows that the number of ordered pairs $(x,y)$ of integers such that $n=x^2+y^2$ is $4(D_1(n)-D_3(n))$.
A: Yet another solution: The result is easily proved when $n$ is a prime power.
If $\gcd(a,b)=1$ then $f(ab)=f(a)f(b)+g(a)g(b)$ and $g(ab)=f(a)g(b)+g(a)f(b)$, and so $f(ab)\ge g(ab)$ by the rearrangement inequality. Now proceed by induction.
A: First prove that if $n=ab2^k$ where $a$ has only prime factors of the form $4n+3$ and $b$ has only prime factors of the form $4n+1$, then $f(n)=d(b)f(a)$ and $g(n)=d(b)g(a)$, where $d(b)$ is the number of divisors of $b$.
Thus it is sufficient to prove it for numbers whose prime factors are all $3$ modulo $4$, so assume that. If at least one of the exponents in the prime factorization is odd, then $f(n)=g(n)$. So assume the exponents are all even. Then, by induction on the number of prime factors we can see that $f(n)=g(n)+1$.
