Sum of two squares theorem

In number theory, the sum of two squares theorem relates the prime decomposition of any integer n > 1 to whether it can be written as a sum of two squares, such that n = a2 + b2 for some integers a, b.

An integer greater than one can be written as a sum of two squares if and only if its prime decomposition contains no prime congruent to modulo raised to an odd power.[1]

This theorem supplements Fermat's theorem on sums of two squares which says when a prime number can be written as a sum of two squares, in that it also covers the case for composite numbers.

Examples

The prime decomposition of the number 2450 is given by 2450 = 2 · 52 · 72. Of the primes occurring in this decomposition, 2, 5, and 7, only 7 is congruent to 3 modulo 4. Its exponent in the decomposition, 2, is even. Therefore, the theorem states that it is expressible as the sum of two squares. Indeed, 2450 = 72 + 492.

The prime decomposition of the number 3430 is 2 · 5 · 73. This time, the exponent of 7 in the decomposition is 3, an odd number. So 3430 cannot be written as the sum of two squares.

gollark: What is it DOING? Why does it turn off the GC? Does the blattidus/2.0 codebase look like this?!
gollark: ... is #9 passing *pointers* over the sockets?
gollark: Besides, you can do that much more nicely with... well, I actually don't know if the sqlite3 python thing provides anything like `CARRAY`, but if it did then that.
gollark: Of actually knowing what `UNION ALL` does?
gollark: Of writing SQL in *lowercase*?

See also

References
  1. Dudley, Underwood (1969). "Sums of Two Squares". Elementary Number Theory. W.H. Freeman and Company. pp. 135–139.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.