This is the Diophantus identity, which results immediately from the similar property of the absolute value. Gaussian integers form a principal ideal domain. This implies that Gaussian primes can be defined similarly as primes numbers, that is as those Gaussian integers that are not the product of two non-units (here the units are and ). The multiplicative property of the norm implies that a prime number is either a Gaussian prime or the norm of a Gaussian prime. Fermat's theorem asserts that the first case occurs when and that the second case occurs when and The last case is not considered in Fermat's statement, but is trivial, as Related results Above point of view on Fermat's theorem is a special case of the theory of factorization of ideals in rings of quadratic integers. In summary, if is the ring of algebraic integers in the quadratic field, then an odd prime number , not dividing , is either a prime element in or the ideal norm of an ideal of which is necessarily prime. Moreover, the law of quadratic reciprocity allows distinguishing the two cases in terms of congruences. If is a principal ideal domain, then is an ideal norm if and only with and both integers. In a letter to Blaise Pascal dated September 25, 1654 Fermat announced the following two results that are essentially the special cases and If is an odd prime, then Fermat wrote also: If two primes which end in 3 or 7 and surpass by 3 a multiple of 4 are multiplied, then their product will be composed of a square and the quintuple of another square. In other words, if are of the form or , then . Euler later extended this to the conjecture that Both Fermat's assertion and Euler's conjecture were established by Joseph-Louis Lagrange. This more complicated formulation relies on the fact that is not a principal ideal domain, unlike and Algorithm There is a trivial algorithm for decomposing a prime of the form into a sum of two squares: For all such , test whether the square root of is an integer. If this the case, one has got the decomposition. However the input size of the algorithm is the number of digits of (up to a constant factor that depends on the numeral base). The number of needed tests is of the order of and thus exponential in the