Sum of two squares theorem

Last updated September 30, 2024

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\equiv 1{\bmod {4}},\ q\equiv 3{\bmod {4}}$ .

$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">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:

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.

In mathematics, a Fermat number, named after Pierre de Fermat, 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, 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.

In number theory, a Wieferich prime is a prime number p such that p² divides $2 p - 1 - 1$ , therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides $2 p - 1 - 1$ . Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.

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.

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.

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.

In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. "Succinct" usually means that the proof should be at most polynomially larger than the number of digits in the number itself.

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.

Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x⁴ ≡ p is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the congruence x⁴ ≡ p to that of x⁴ ≡ q.

In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form

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: 579–580.

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: 579–580.

[1]

[2]

[3]

[4]

[5]

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