View source for Sum of two squares theorem

{{short description|Characterization by prime factors of sums of two squares}}
[[File:Sum_of_two_squares_theorem.svg|thumb|upright=1.5|Integers satisfying the sum of two squares theorem are squares of possible distances between integer lattice points; values up to 100 are shown, with
{|
|valign="top"|•||Squares (and thus integer distances) in red, and
|-
|valign="top"|•||Non-unique representations (up to rotation and reflection) bolded
|} ]]
In [[number theory]], the '''sum of two squares theorem''' relates the [[prime decomposition]] of any [[integer]] {{math|{{var|n}} > 1}} to whether it can be written as a sum of two [[Square number|squares]], such that {{math|1={{var|n}} = {{var|a}}{{sup|2}} + {{var|b}}{{sup|2}}}} for some integers {{mvar|a}}, {{mvar|b}}.<ref>{{cite book
 | last = Dudley | first = Underwood | author-link = Underwood Dudley
 | title = Elementary Number Theory
 | year = 1969
 | publisher = W.H. Freeman and Company
 | chapter = Sums of Two Squares
 | pages = 135–139}}</ref>

<blockquote>An integer greater than one can be written as a sum of two squares [[if and only if]] its [[prime decomposition]] contains no factor {{math|{{var|p}}{{sup|''k''}}}}, where [[Prime number|prime]] <math>p \equiv 3 \pmod 4</math> and {{math|1=''k''}} is [[Parity (mathematics)|odd]].</blockquote>

In writing a number as a sum of two squares, it is allowed for one of the squares to be zero, or for both of them to be equal to each other, so all squares and all doubles of squares are included in the numbers that can be represented in this way. 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 number]]s.

A number may have multiple representations as a sum of two squares, counted by the [[sum of squares function]]; for instance, every [[Pythagorean triple]] <math>a^2+b^2=c^2</math> gives a second representation for <math>c^2</math> beyond the trivial representation <math>c^2+0^2</math>.

==Examples==
The prime decomposition of the number 2450 is given by 2450 = 2{{middot}}5{{sup|2}}{{middot}}7{{sup|2}}. 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 [[Parity (mathematics)|even]]. Therefore, the theorem states that it is expressible as the sum of two squares. Indeed, {{math|1=2450 = 7{{sup|2}} + 49{{sup|2}}}}.

The prime decomposition of the number 3430 is 2{{middot}}5{{middot}}7{{sup|3}}. 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.

==Representable numbers==
The numbers that can be represented as the sums of two squares form the [[integer sequence]]<ref name=oeis>{{cite OEIS|A001481|Numbers that are the sum of 2 squares}}</ref>
:0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, ...
They form the set of all [[Field norm|norms]] of [[Gaussian integer]]s;<ref name=oeis/> their square roots form the set of all lengths of [[line segment]]s between pairs of points in the two-dimensional [[integer lattice]].

The number of representable numbers in the range from 0 to any number <math>n</math> is proportional to <math>\frac{n}{\sqrt{\log n}}</math>, with a limiting constant of proportionality given by the [[Landau–Ramanujan constant]], approximately 0.764.<ref>{{cite journal | last = Rebák | first = Örs | doi = 10.1080/00029890.2020.1668716 | issue = 1 | journal = [[The American Mathematical Monthly]] | mr = 4043992 | pages = 80–83 | title = Generalization of a Ramanujan identity | volume = 127 | year = 2020| arxiv = 1612.08307 }}</ref>

The product of any two representable numbers is another representable number. Its representation can be derived from representations of its two factors, using the [[Brahmagupta–Fibonacci identity]].

== Jacobi's two-square theorem ==

{{Math theorem
| math_statement = 
Denote the [[number of divisors]] of <math>n</math> as <math>d(n)</math>, and write <math>d_a(n)</math> for the number of those divisors with <math>d \equiv a \bmod 4</math>. Let <math>n = 2^f p_1 ^{r_1} p_2 ^ {r_2} \cdots q_1^{s_1} q_2^{s_2} \cdots </math> where <math>p_i \equiv 1 \bmod 4, \ q_i \equiv 3 \bmod 4</math>.

Let <math>r_2(n)</math> be the number of ways <math>n</math> can be represented as the sum of two squares.

Then, <math>r_2(n) = 0</math> if any of the exponents <math>s_j</math> are odd. If all <math>s_j</math> are even, then <math display="block">r_2(n) = 4 d (p_1^{r_1} p_2^{r_2} \cdots ) = 4(d_1(n) - d_3(n)) </math>
| name = Two-square theorem
}} Proved by Gauss using [[Quadratic form|quadratic forms]] and Jacobi using [[Elliptic function|elliptic functions]].<ref name=":0">{{Cite book |last=Grosswald |first=Emil |title=Representations of integers as sums of squares |date=1985 |publisher=Springer |isbn=978-3-540-96126-0 |location=New York Berlin Heidelberg [etc.] |pages=15–19}}</ref> An elementary proof is based on the [[Unique factorization domain|unique factorization]] of the [[Gaussian integer|Gaussian integers]].<ref name=":0" /> Hirschhorn gives a short proof derived from the [[Jacobi triple product]].<ref>{{Cite journal |last=Hirschhorn |first=Michael |year=1985 |title=A simple proof of Jacobi's two-square theorem |url=https://web.maths.unsw.edu.au/~mikeh/webpapers/paper21.pdf |journal=Amer. Math. Monthly |volume=92 |issue=8 |pages=579–580|doi=10.1080/00029890.1985.11971686 }}</ref>

== See also ==
* [[Legendre's three-square theorem]]
* [[Lagrange's four-square theorem]]
* [[Sum of squares function]]
* [[Brahmagupta–Fibonacci identity]]

==References==
{{reflist}}

[[Category:Additive number theory]]
[[Category:Squares in number theory]]
[[Category:Theorems in number theory]]