Prove the following:
If $n$ is the product of $r$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is $2^{r−1}$.
We will prove this by induction.
Let $S(r)$ be the statement:
If $n$ is the product of $r$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is $2^{r−1}$.
We need to prove the base case $S(1)$ and the inductive step $S(r) \implies S(r+1)$.
Base Case $S(1)$
The base case is
If $n$ is the product of 1 distinct prime $p$ which satisfies $p \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is 1.
In the previous exercise we showed that a prime $p_j$ satisfying $p_j \equiv 1 \pmod 4$ can be written uniquely as a sum of squaresm, which proves the base case.
Induction Step $S(r) \implies S(r+1)$
The statement $S(r+1)$ is
If $n$ is the product of $r+1$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is $2^{r}$.
We assume $S(r)$ as the induction hypothesis
If $m$ is the product of $r$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $m$ can be expressed as a sum of two squares is $2^{r−1}$.
Here $n = m \times p$ where $p$ is distinct from any prime in $m$ and satisfies $p \equiv 1 \pmod p$.
Since $p$ can be uniquely written as a sum of squares, $p=a^2 +b^2$, we have
$$ n = m \times (a^2 + b^2) $$
But $m$ can also be written as a sum of squares, $m = c^2+d^2$, we have by the two conversion identities
$$ n = (c^2 + d^2) \times (a^2 + b^2) = (ca-db)^2 + (cb+da)^2 $$
$$ n = (c^2 + d^2) \times (a^2 + b^2) = (ca+db)^2 + (cb-da)^2 $$
We now show the sums of squares are distinct:
- If $ac-bd = ac+bd$ then$bd=0$ implying $b=0$ or $d=0$. If $b=0$ then $p=a^2$, which contradicts $p$ is prime. If $d=0$ that would imply $n=c^2$, and this contradicts $n$ being the product of distinct primes. So $ac+bd \ne ac-bd$.
- If $ac-bd = cb-da$ then $c(a-b)=-d(a-b)$, and so $c=-d$, which means $m=2c^2$, contradicting $m$ being a product of distinct primes. So $ac-bd \ne cb-da$.
- If $cb+da=cb-da$ then $da=0$ implying $a=0$ or $d=0$. If $a=0$ then $p=b^2$, which contradicts $p$ is prime. If $d=0$ that would imply $n=c^2$, and this contradicts $n$ being the product of distinct primes. So $cb+da \ne cb-da$.
- If $cb+da = ca+db$ then $c(b-a)=d(b-a)$m and so $c=d$, which means $m=2c^2$, contradicting $m$ being a product of distinct primes. So $cb+da \ne ca+db$.
By assumption $m$ can be written as a sum of squares in $2^{r-1}$ ways, and since $p$ can be written in two ways, this means $n$ can be written as a sum of squares in $2^{r-1}\times 2 = 2^r$ was, proving the induction step.
By induction we have shown that if $n$ is the product of $r$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is $2^{r−1}$.
Note: there is an unproven assumption here, and in the author's solution, that $(c^2 + d^2) \times (a^2 + b^2)$ can be written in two different forms, $(ca-db)^2 + (cb+da)^2 $ and $(ca+db)^2 + (cb-da)^2$, and no more.