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 Diophantes' \(Arithmetica\) the third century AD, and was later 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, \(a, b, c\), and \(d\).
\[\begin{align} (a^2 + b^2)(c^2 + d^2) = a^2c^2 + a^2d^2 + b^2c^2 +b^2d^2 &= a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2 - 2abcd + 2abcd \\ &= (a^2c^2 \pm 2abcd + b^2d^2) + (a^2d^2 \mp 2abcd + b^2c^2) \\ &= (ac \pm bd)^2 + (ad \mp bc)^2 \end{align}\]
Note, that in general it is the sum of two squares in two different ways, except for when
\(|ac + bd| = |ad + bc|\) and \(|ac - bd| = |ad - bc|\)
for example if \(a=b=c\) and \(d=0\) or \(a=b=c=d\).
Finally, note that for \(a = b\) and \(c = d\), you have:
\((a^2 + b^2)(c^2 + d^2) = (2ac)^2\) which is \(0^2 + (2ac)^2\), which is still the sum of two squares.
Examples
For example, lets consider the integers 1, 2, 3, and 4.
\((1^2 + 2^2)(3^2 + 4^2) = (1\cdot 3 + 2 \cdot 4)^2 + (1\cdot 4 - 2 \cdot 3)^2 = 11^2 + 2^2 = 125\)
\((1^2 + 2^2)(3^2 + 4^2) = (1\cdot 3 - 2 \cdot 4)^2 + (1\cdot 4 + 2 \cdot 3)^2 = 5^2 + 10^2 = 125\)
For an integer \(N\), can \(N^4+13N+36\) be written as the sum of two squares?
Factoring \(N^4+13N^2+36\) we get:
\(N^4+13N^2+36 = (N^2+9)(N^2+4)\)
This is the product of two numbers that are the sum of two squares.
Therefore, \boxed{\text{yes}}, by the Diophantus' identity, it can be written by the sum of two squares, (in fact in two different ways) as follows:
\(N^4+13N+36 = (N^2 + 6)^2 + N^2\)
and
\(N^4+13N+36 = (N^2 - 6)^2 + (5N)^2\)