Sum of two squares theorem

Last updated January 06, 2025

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 = a 2 + b 2$ for some integers $a$ , $b$ .^[1]

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 numbers.

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

Examples

The prime decomposition of the number 2450 is given by 2450 = 2 ·5² ·7². 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 = 7 2 + 49 2$ .

The prime decomposition of the number 3430 is 2 ·5 ·7³. 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 ^[2]

0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, ...

They form the set of all norms of Gaussian integers;^[2] their square roots form the set of all lengths of line segments between pairs of points in the two-dimensional integer lattice.

The number of representable numbers in the range from 0 to any number $n$ is proportional to ${\frac {n}{\sqrt {\log n}}}$ , with a limiting constant of proportionality given by the Landau–Ramanujan constant, approximately 0.764.^[3]

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

Two-square theorem — Denote the number of divisors of $n$ as $d(n)$ , and write $d_{a}(n)$ for the number of those divisors with $d\equiv a{\bmod {4}}$ . Let $n=2^{f}p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots q_{1}^{s_{1}}q_{2}^{s_{2}}\cdots$ where $p_{i}\equiv 1{\bmod {4}},\ q_{i}\equiv 3{\bmod {4}}$ .

Let $r_{2}(n)$ be the number of ways $n$ can be represented as the sum of two squares.

Then, $r_{2}(n)=0$ if any of the exponents $s_{j}$ are odd. If all $s_{j}$ are even, then $r_{2}(n)=4d(p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots )=4(d_{1}(n)-d_{3}(n))$

Proved by Gauss using quadratic forms and Jacobi using elliptic functions.^[4] An elementary proof is based on the unique factorization of the Gaussian integers.^[4] Hirschhorn gives a short proof derived from the Jacobi triple product.^[5]

Related Research Articles

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number ⁠ $⁠$ which in modular arithmetic satisfies the congruence relation:

<span class="mw-page-title-main">Prime number</span> Number divisible only by 1 or itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

<span class="mw-page-title-main">Quadratic reciprocity</span> Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

In mathematics, a Fermat number, named after Pierre de Fermat (1607–1665), the first known to have studied them, is a positive integer of the form: $where n is a non-negative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ....$

In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n is also a positive integer. In other words, there are infinitely many primes that are congruent to a modulo d. The numbers of the form a + nd form an arithmetic progression

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite, the condition is generally chosen in order to make such exceptions rare.

The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.

In number theory, quadratic Gauss sums are certain finite sums of roots of unity. A quadratic Gauss sum can be interpreted as a linear combination of the values of the complex exponential function with coefficients given by a quadratic character; for a general character, one obtains a more general Gauss sum. These objects are named after Carl Friedrich Gauss, who studied them extensively and applied them to quadratic, cubic, and biquadratic reciprocity laws.

In number theory, the Kronecker symbol, written as $or, is a generalization of the Jacobi symbol to all integers . It was introduced by Leopold Kronecker.$

Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.

<span class="mw-page-title-main">Carmichael function</span> Function in mathematical number theory

In number theory, a branch of mathematics, the Carmichael function $λ (n)$ of a positive integer $n$ is the smallest positive integer $m$ such that

In mathematics, the interplay between the Galois group G of a Galois extension L of a number field K, and the way the prime ideals P of the ring of integers O_K factorise as products of prime ideals of O_L, provides one of the richest parts of algebraic number theory. The splitting of prime ideals in Galois extensions is sometimes attributed to David Hilbert by calling it Hilbert theory. There is a geometric analogue, for ramified coverings of Riemann surfaces, which is simpler in that only one kind of subgroup of G need be considered, rather than two. This was certainly familiar before Hilbert.

The Ramanujan tau function, studied by Ramanujan, is the function $:\mathbb {N} \rightarrow \mathbb {Z} }$ defined by the following identity:

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number $p$ , then this root can be lifted to a unique root modulo any higher power of $p$ . More generally, if a polynomial factors modulo $p$ into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of $p$ .

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

In mathematics, a Kloosterman sum is a particular kind of exponential sum. They are named for the Dutch mathematician Hendrik Kloosterman, who introduced them in 1926 when he adapted the Hardy–Littlewood circle method to tackle a problem involving positive definite diagonal quadratic forms in four variables, strengthening his 1924 dissertation research on five or more variables.

The Blum–Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum–Goldwasser is a probabilistic, semantically secure cryptosystem with a constant-size ciphertext expansion. The encryption algorithm implements an XOR-based stream cipher using the Blum-Blum-Shub (BBS) pseudo-random number generator to generate the keystream. Decryption is accomplished by manipulating the final state of the BBS generator using the private key, in order to find the initial seed and reconstruct the keystream.

Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x³ ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence x³ ≡ p is solvable if and only if x³ ≡ q is solvable.

In number theory, the sum of squares function is an arithmetic function that gives the number of representations for a given positive integer $n$ as the sum of $k$ squares, where representations that differ only in the order of the summands or in the signs of the numbers being squared are counted as different. It is denoted by $r k (n)$ .

References

↑ Dudley, Underwood (1969). "Sums of Two Squares". Elementary Number Theory. W.H. Freeman and Company. pp. 135–139.
1 2 Sloane, N. J. A. (ed.). "SequenceA001481(Numbers that are the sum of 2 squares)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.
↑ Rebák, Örs (2020). "Generalization of a Ramanujan identity". The American Mathematical Monthly . 127 (1): 80–83. arXiv: 1612.08307 . doi:10.1080/00029890.2020.1668716. MR 4043992.
1 2 Grosswald, Emil (1985). Representations of integers as sums of squares. New York Berlin Heidelberg [etc.]: Springer. pp. 15–19. ISBN 978-3-540-96126-0.
↑ Hirschhorn, Michael (1985). "A simple proof of Jacobi's two-square theorem" (PDF). Amer. Math. Monthly. 92 (8): 579–580. doi:10.1080/00029890.1985.11971686.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Dudley, Underwood (1969). "Sums of Two Squares". Elementary Number Theory. W.H. Freeman and Company. pp. 135–139.

[oeis-2] 1 2 Sloane, N. J. A. (ed.). "SequenceA001481(Numbers that are the sum of 2 squares)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.

[3] Rebák, Örs (2020). "Generalization of a Ramanujan identity". The American Mathematical Monthly . 127 (1): 80–83. arXiv: 1612.08307 . doi:10.1080/00029890.2020.1668716. MR 4043992.

[:0-4] 1 2 Grosswald, Emil (1985). Representations of integers as sums of squares. New York Berlin Heidelberg [etc.]: Springer. pp. 15–19. ISBN 978-3-540-96126-0.

[5] Hirschhorn, Michael (1985). "A simple proof of Jacobi's two-square theorem" (PDF). Amer. Math. Monthly. 92 (8): 579–580. doi:10.1080/00029890.1985.11971686.

[1]

[2]

[3]

[4]

[5]

•	Squares (and thus integer distances) in red, and
•	Non-unique representations (up to rotation and reflection) bolded