First, what if \(N\) has only primes of the form \(4k+1\) and \(2\) as factors?

• Then each of those primes is in \(S_2\), so we can use the Brahmagupta-Fibonacci identity to write the intermediate products that way.
• E.g., \[2\cdot 13\cdot 17=442 = \left(1^2+1^2\right)\left( 3^2+2^2\right)\cdot 17 \]\[= \left[\left(1\cdot 3-1\cdot 2\right)^2+\left(1\cdot 2+1\cdot 3\right)^2\right]\left(4^2+1^2\right)\] \[=\left(1^2+5^2\right)\left(4^2+1^2\right)=\left(1\cdot 4-5\cdot 1\right)^2+\left(1\cdot 1+5\cdot 4\right)^2=1^2+21^2\]

Next, what if \(N\) has primes of the form \(4k+3\), but only to even powers?

• We saw last time that \(p^2\) is always in \(S_2\) trivially, since \(p^2=p^2+0^2\).
• So for each factor of \(p^2\), we can do this again. In fact, we just have to multiply each term by \(p^2\)!
• E.g., \[35802=442\cdot 3^4 = \left(1^2+21^2\right)3^2\cdot 3^2\]\[=1^2\cdot 3^2\cdot 3^2+21^2\cdot 3^2\cdot 3^2=9^2+189^2\]

What if \(N\) had a prime of the form \(p=4k+3\) to an odd power?

• This seemed to be the bottleneck in our exploration.
• Suppose that it is possible to write \[N=a^2+b^2\; .\]
• Divide this equation by any factors of \(p\) common to both sides to get \[M=c^2+d^2\, .\] (This must actually be an even power of \(p\), since the right-hand side is made up of squares and can only contribute even powers of primes.)
• Now \(M\) still has an odd power of \(p\) dividing it, but \(p\nmid c,d\). Take everything modulo \(p\) to get \[0\equiv c^2+d^2\text{ mod }(p)\; .\]
• Since \(p \nmid c\), we can multiply this congruence by \(\left(c^{-1}\right)^2\) to get \[0\equiv 1+\left(c^{-1}\right)^2d^2\Rightarrow -1\equiv \left(c^{-1}d\right)^2\text{ mod }(p)\]
• There is no square root of \(-1\) modulo \(p\), however, so our supposition that \(N=a^2+b^2\) is impossible.