How can we prove that we have $2^{k-1}$ distinct representations as a sum of two squares?

Question

Let $n$ be the product of $k$ distinct prime numbers of the form $4m+1$.

How can I prove that the number of solutions $n=a^2+b^2$ with integers $a,b$ satisfying $0<a<b$ is $2^{k-1}$ ?

I tried to use the idendity $$(a^2+b^2)(c^2+d^2)=(ad+bc)^2+(ac-bd)^2$$ and induction over the number of prime factors , but the problem is to show that the representations I get this way are actually distinct , so that the number of representations actually doubles with every new prime factor.

Answer 1

Let's show that the number of solutions $(a, b)$ with $0 \leq a, b$ equals $2^{k}$. Because $n$ is square-free, this implies that the number of solutions with $0 < a < b$ is $2^{k-1}$.

Call $R_2(n)$ the set of solutions $(a, b)$ with $0 \leq a, b$. Call $P(n)$ the set of ideals of $\mathbb Z[i]$ of norm $n$. The number of such ideals is equal to $2^k$, by unique factorization of ideals. We have a map $f : R_2(n) \to P(n)$ that sends $(a, b)$ to $(a+bi)$.

• $f$ is surjective: Take an ideal of norm $n$, which is generated by some $\alpha \in \mathbb Z[i]$ of norm $n$, say $\alpha = a+bi$. If $a, b$ have different signs, multiply by $i$. If $a, b \leq 0$, multiply by $-1$. We may thus assume $a, b \geq 0$.
• $f$ is injective: Suppose $a, b, c, d \geq 0$ and $a+bi = i^k (c+di)$ for some $k \in \{0, 1, 2, 3\}$. If $k = 0$, we are done. If $k = 1$, $a = -d = 0$ so that $n = b^2$ is a square, a contradiction. Similarly if $k = 2, 3$.

Answer 2

Let $$n=\prod_{j=1}^kp_j$$ Then $p_j$ has a unique representation $p_j=a_j^2+b_j^2=\lvert a_j+ib_j\rvert^2=\lvert q_j\rvert^2$ where $q_j=a_j+ib_j$, $a_j>b_j>0$. Let $r_j\in\{q_j,q_j^*\}$ and choose $0\le\ell\le3$ such that $$a+ib=i^{\ell}\prod_{j=1}^kr_j$$ and $a>|b|>0$. So there are $2^k$ representations. How can we tell them apart? Multiply by $q_j$. If $p_j\operatorname{|}\Re(a+ib)q_j$, then we know that $r_j=q_j^*$. If not, then $r_j=q_j$. If we now consider the representations with opposite signs of $b$ to be equivalent, then we are down to $2^{k-1}$ representations.