Is the number of ways to express a number as sum of two coprime squares same as number of solution of $x^2+1\equiv0\pmod n$

Question

The number of representations of $n$ by sum of 2 squares is known as sum of square function $r_2 (n)$. It is known that if prime factorization of $n$ is given as $$2^{a_0}p_1^{a_1}p_2^{a_2}\cdots q_1^{b_1}q_2^{b_2}\cdots$$ , where $p_i$s are primes of the form $4k+1$ and $q_i$s are primes of $4k+3$, then $r_2 (n)=0$ if any of $b_i$ is odd and $r_2 (n)=4(a_1+1)(a_2+1)\cdots$ if not.

However, I can't find any result that counts the number of representations of $n$ by sum of 2 coprime squares given its factorization. Can you find one?

By simple brute force and searching OEIS, I found that https://oeis.org/A000089 looks nearly identical to the function $r_{2, coprime}(n)$ I explained.

Can you prove or disprove $r_{2, coprime}(n) = A000089(n)$?

Answer 1

We will just use that $\mathbb{Z}[i]$ is a factorial ring. As before $n=\prod_{i=1}^{k}p_i^{\alpha_i}$ where $p_1=2$ and $\alpha_1=0,1$ or $p_i\equiv 1 \pmod{4}$ for $i\geq 2$. Then each $p_i$ with $i\geq 2$ factors uniquely as $q_i\overline{q_i}$. Writing $n=a^2+b^2$ corresponds to factoring $n$ as $(a+bi)(a-bi)$ where $(a+bi)$ and $(a-bi)$ are corpime. Then the statement is clear each factor of $(a+bi)$ is either $q_i^{\alpha_i}$ or $\overline{q_i}^{\alpha_i}$, and if you have $2|n$ you also have a choice for $(1+i)$ and $(1-i)$. Thus you get exactly $2^k$ such writings.