Number Theory | Sums of Squares Part 4

We provide a few examples of writing natural numbers as sums of two squares.

[fernandoalmer]

do you have like a theorem for an n that is expressible as more than 1 sum of two squares?

[ThePharphis]

Wow, this property is quite interesting.


At first I was confused due to the negatives, but since you're squaring all the terms if doesn't matter which number you consider negative or not - so always choose the lower number as negative for easier mental subtraction.


I was wondering what computational complexity this algorithm has? I'm guessing logarithmic, or perhaps n logn


I was also wondering if the expression will always be of the form
x^2 + y^2 =
x^2 + (zx)^2 =
(z^2 + 1)x^2


ie x always divides y?
I ask because of my comment on the previous video - I'm wondering if systematically checking all perfect squares (+1) below the number, n, we are trying to express will *always* provide a solution or if this algorithm you've shown will sometimes produce an expression of a different form?


Thanks again for all your work