Diophantus' Identity
Diophantus' identity (also known as the Brahmagupta–Fibonacci identity) states the following:
If two positive integers are each the sum of two squares, then their product is the sum of two squares.
It was originally found in Diophantus' the third century AD and was generalized by Brahmagupta about 400 years later.
Diophantus' identity is an example of many sum of squares theorems that have been used for both cryptography and integer factoring algorithms.
Proof
We can prove this identity as follows:
Consider four integers, , and
Note that, in general, it is the sum of two squares in two different ways, except for when
for example, if and or .
Finally, note that for and , you have
which is , which is still the sum of two squares.
Examples
For example, let's consider the integers 1, 2, 3, and 4:
For an integer , can be written as the sum of two squares?
Factoring we get
This is the product of two numbers that are the sum of two squares.
Therefore, yes, by the Diophantus' identity, it can be written by the sum of two squares. In fact, it can be written in two different ways as follows: