additive number theory
Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigr ...
,
Fermat
Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he is ...
's theorem on sums of two squares states that an
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
prime
A prime number (or a prime) 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 ...
''p'' can be expressed as:
:
with ''x'' and ''y'' integers,
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
:
The prime numbers for which this is true are called Pythagorean primes.
For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1
modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is ...
4, and they can be expressed as sums of two squares in the following ways:
:
On the other hand, the primes 3, 7, 11, 19, 23 and 31 are all congruent to 3 modulo 4, and none of them can be expressed as the sum of two squares. This is the easier part of the theorem, and follows immediately from the observation that all squares are congruent to 0 or 1 modulo 4.
Since the Diophantus identity implies that the product of two integers each of which can be written as the sum of two squares is itself expressible as the sum of two squares, by applying Fermat's theorem to the prime factorization of any positive integer ''n'', we see that if all the prime factors of ''n'' congruent to 3 modulo 4 occur to an even exponent, then ''n'' is expressible as a sum of two squares. The converse also holds. This generalization of Fermat's theorem is known as the
sum of two squares theorem
In number theory, the sum of two squares theorem relates the prime decomposition of any integer to whether it can be written as a sum of two squares, such that for some integers , .
:''An integer greater than one can be written as a sum of t ...
.
History
Albert Girard
Albert Girard () (11 October 1595 in Saint-Mihiel, France − 8 December 1632 in Leiden, The Netherlands) was a French-born mathematician. He studied at the University of Leiden. He "had early thoughts on the fundamental theorem of algebra" and ...
was the first to make the observation, describing all positive integer numbers (not necessarily primes) expressible as the sum of two squares of positive integers; this was published in 1625. The statement that every prime ''p'' of the form ''4n+1'' is the sum of two squares is sometimes called ''Girard's theorem''. For his part, Fermat wrote an elaborate version of the statement (in which he also gave the number of possible expressions of the powers of ''p'' as a sum of two squares) in a letter to
Marin Mersenne
Marin Mersenne, OM (also known as Marinus Mersennus or ''le Père'' Mersenne; ; 8 September 1588 – 1 September 1648) was a French polymath whose works touched a wide variety of fields. He is perhaps best known today among mathematicians for ...
dated December 25, 1640: for this reason this version of the theorem is sometimes called ''Fermat's Christmas theorem.''
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the fo ...
such that and are integers. The ''norm'' of a Gaussian integer is an integer equal to the square of the
absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), ...
of the Gaussian integer. The norm of a product of Gaussian integers is the product of their norms. This is the Diophantus identity, which results immediately from the similar property of the absolute value.
Gaussian integers form a
principal ideal domain
In mathematics, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principa ...
. 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
prime element
In mathematics, specifically in abstract algebra, a prime element of a commutative ring is an object satisfying certain properties similar to the prime numbers in the integers and to irreducible polynomials. Care should be taken to distinguish pri ...
in or the
ideal norm In commutative algebra, the norm of an ideal is a generalization of a norm of an element in the field extension. It is particularly important in number theory since it measures the size of an ideal of a complicated number ring in terms of an idea ...
of an ideal of which is necessarily prime. Moreover, the
law of quadratic reciprocity
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 ...
allows distinguishing the two cases in terms of congruences. If is a
principal ideal domain
In mathematics, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principa ...
, then is an ideal norm if and only
:
with and both integers.
In a letter to
Blaise Pascal
Blaise Pascal ( , , ; ; 19 June 1623 – 19 August 1662) was a French mathematician, physicist, inventor, philosopher, and Catholic writer.
He was a child prodigy who was educated by his father, a tax collector in Rouen. Pascal's earliest ...
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
Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangiaalgorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
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
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
*Exponential decay, decrease at a rate proportional to value
*Expo ...
in the input size. So the
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
of this algorithm is
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
*Exponential decay, decrease at a rate proportional to value
*Expo ...
.
An algorithm with a polynomial complexity has been described by
Stan Wagon in 1990, based on work by Serret and Hermite (1848), and Cornacchia (1908).
Description
Given an odd prime in the form , first find such that .
This can be done by finding a
Quadratic non-residue
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that:
:x^2\equiv q \pmod.
Otherwise, ''q'' is called a quadratic ...
modulo , say , and letting
.
Such an will satisfy the condition since quadratic non-residues satisfy .
Once is determined, one can apply the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an e ...
with and . Denote the first two remainders that are less than the square root of as and . Then it will be the case that .
Example
Take . A possible quadratic non-residue for 97 is 13, since . so we let .
The Euclidean algorithm applied to 97 and 22 yields:
The first two remainders smaller than the square root of 97 are 9 and 4; and indeed we have , as expected.
Proofs
Fermat usually did not write down proofs of his claims, and he did not provide a proof of this statement. The first proof was found by
Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ...
after much effort and is based on
infinite descent In mathematics, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of proof by contradiction used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold f ...
. He announced it in two letters to Goldbach, on May 6, 1747 and on April 12, 1749; he published the detailed proof in two articles (between 1752 and 1755).
Lagrange
Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangiaquadratic forms. This proof was simplified by Gauss in his '' Disquisitiones Arithmeticae'' (art. 182). Dedekind gave at least two proofs based on the arithmetic of the Gaussian integers. There is an elegant proof using Minkowski's theorem about convex sets. Simplifying an earlier short proof due to
Heath-Brown
David Rodney "Roger" Heath-Brown FRS (born 12 October 1952), is a British mathematician working in the field of analytic number theory.
Education
He was an undergraduate and graduate student of Trinity College, Cambridge; his research supervis ...
(who was inspired by Liouville's idea), Zagier presented a non-constructive one-sentence proof in 1990.
And more recently Christopher gave a partition-theoretic proof.
Euler's proof by infinite descent
Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ...
succeeded in proving Fermat's theorem on sums of two squares in 1749, when he was forty-two years old. He communicated this in a letter to Goldbach dated 12 April 1749. The proof relies on
infinite descent In mathematics, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of proof by contradiction used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold f ...
, and is only briefly sketched in the letter. The full proof consists in five steps and is published in two papers. The first four steps are Propositions 1 to 4 of the first paper and do not correspond exactly to the four steps below. The fifth step below is from the second paper.
For the avoidance of ambiguity, zero will always be a valid possible constituent of "sums of two squares", so for example every square of an integer is trivially expressible as the sum of two squares by setting one of them to be zero.
1. ''The product of two numbers, each of which is a sum of two squares, is itself a sum of two squares.''
::This is a well-known property, based on the identity
:::
::due to
Diophantus
Diophantus of Alexandria ( grc, Διόφαντος ὁ Ἀλεξανδρεύς; born probably sometime between AD 200 and 214; died around the age of 84, probably sometime between AD 284 and 298) was an Alexandrian mathematician, who was the aut ...
.
2. ''If a number which is a sum of two squares is divisible by a prime which is a sum of two squares, then the quotient is a sum of two squares.''
(This is Euler's first Proposition).
::Indeed, suppose for example that is divisible by and that this latter is a prime. Then divides
:::
::Since is a prime, it divides one of the two factors. Suppose that it divides . Since
:::
::(Diophantus's identity) it follows that must divide . So the equation can be divided by the square of . Dividing the expression by yields:
:::
::and thus expresses the quotient as a sum of two squares, as claimed.
::On the other hand if divides , a similar argument holds by using the following variant of Diophantus's identity:
:::
3. ''If a number which can be written as a sum of two squares is divisible by a number which is not a sum of two squares, then the quotient has a factor which is not a sum of two squares.'' (This is Euler's second Proposition).
::Suppose is a number not expressible as a sum of two squares, which divides . Write the quotient, factored into its (possibly repeated) prime factors, as so that . If all factors can be written as sums of two squares, then we can divide successively by , , etc., and applying step (2.) above we deduce that each successive, smaller, quotient is a sum of two squares. If we get all the way down to then itself would have to be equal to the sum of two squares, which is a contradiction. So at least one of the primes is not the sum of two squares.
4. ''If and are relatively prime positive integers then every factor of is a sum of two squares.''
(This is the step that uses step (3.) to produce an 'infinite descent' and was Euler's Proposition 4. The proof sketched below also includes the proof of his Proposition 3).
::Let be relatively prime positive integers:
without loss of generality
''Without loss of generality'' (often abbreviated to WOLOG, WLOG or w.l.o.g.; less commonly stated as ''without any loss of generality'' or ''with no loss of generality'') is a frequently used expression in mathematics. The term is used to indicat ...
is not itself prime, otherwise there is nothing to prove. Let therefore be a ''proper'' factor of , not necessarily prime: we wish to show that is a sum of two squares. Again, we lose nothing by assuming since the case is obvious.
::Let be non-negative integers such that are the closest multiples of (in absolute value) to respectively. Notice that the differences and are integers of absolute value strictly less than : indeed, when is even, gcd; otherwise since gcd, we would also have gcd.
::Multiplying out we obtain
:::
::uniquely defining a non-negative integer . Since divides both ends of this equation sequence it follows that must also be divisible by : say . Let be the gcd of and which by the co-primeness of is relatively prime to . Thus divides , so writing , and , we obtain the expression for relatively prime and , and with , since
:::
::Now finally, the ''descent'' step: if is not the sum of two squares, then by step (3.) there must be a factor say of which is not the sum of two squares. But and so repeating these steps (initially with in place of , and so on ''ad infinitum'') we shall be able to find a strictly decreasing infinite sequence of positive integers which are not themselves the sums of two squares but which divide into a sum of two relatively prime squares. Since such an infinite descent is impossible, we conclude that must be expressible as a sum of two squares, as claimed.
5. ''Every prime of the form is a sum of two squares.''
(This is the main result of Euler's second paper).
::If , then by
Fermat's Little Theorem
Fermat's little theorem states that if ''p'' is a prime number, then for any integer ''a'', the number a^p - a is an integer multiple of ''p''. In the notation of modular arithmetic, this is expressed as
: a^p \equiv a \pmod p.
For example, if = ...
each of the numbers is congruent to one modulo . The differences are therefore all divisible by . Each of these differences can be factored as
:::
::Since is prime, it must divide one of the two factors. If in any of the cases it divides the first factor, then by the previous step we conclude that is itself a sum of two squares (since and differ by , they are relatively prime). So it is enough to show that cannot always divide the second factor. If it divides all differences , then it would divide all differences of successive terms, all differences of the differences, and so forth. Since the th differences of the sequence are all equal to (
Finite difference
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for t ...
), the th differences would all be constant and equal to , which is certainly not divisible by . Therefore, cannot divide all the second factors which proves that is indeed the sum of two squares.
Lagrange's proof through quadratic forms
Lagrange
Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangiaquadratic form
In mathematics, a quadratic form is a polynomial with terms all of degree two ("form" is another name for a homogeneous polynomial). For example,
:4x^2 + 2xy - 3y^2
is a quadratic form in the variables and . The coefficients usually belong to ...
s. The following presentation incorporates a slight simplification of his argument, due to Gauss, which appears in article 182 of the Disquisitiones Arithmeticae.
An (integral binary) quadratic form is an expression of the form with integers. A number is said to be ''represented by the form'' if there exist integers such that . Fermat's theorem on sums of two squares is then equivalent to the statement that a prime is represented by the form (i.e., , ) exactly when is congruent to modulo .
The
discriminant
In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the roots without computing them. More precisely, it is a polynomial function of the coefficients of the orig ...
of the quadratic form is defined to be . The discriminant of is then equal to .
Two forms and are ''equivalent'' if and only if there exist substitutions with integer coefficients
:
:
with such that, when substituted into the first form, yield the second. Equivalent forms are readily seen to have the same discriminant, and hence also the same parity for the middle coefficient , which coincides with the parity of the discriminant. Moreover, it is clear that equivalent forms will represent exactly the same integers, because these kind of substitutions can be reversed by substitutions of the same kind.
Lagrange proved that all positive definite forms of discriminant −4 are equivalent. Thus, to prove Fermat's theorem it is enough to find ''any'' positive definite form of discriminant −4 that represents . For example, one can use a form
:
where the first coefficient ''a'' = was chosen so that the form represents by setting ''x'' = 1, and ''y'' = 0, the coefficient ''b'' = 2''m'' is an arbitrary even number (as it must be, to get an even discriminant), and finally is chosen so that the discriminant is equal to −4, which guarantees that the form is indeed equivalent to . Of course, the coefficient must be an integer, so the problem is reduced to finding some integer ''m'' such that divides : or in other words, a '' 'square root of -1 modulo ' ''.
We claim such a square root of is given by . Firstly it follows from Euclid's
Fundamental Theorem of Arithmetic
In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the ord ...
that . Consequently, : that is, are their own inverses modulo and this property is unique to them. It then follows from the validity of Euclidean division in the integers, and the fact that is prime, that for every the gcd of and may be expressed via the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an e ...
yielding a unique and ''distinct'' inverse of modulo . In particular therefore the product of ''all'' non-zero residues modulo is . Let : from what has just been observed, . But by definition, since each term in may be paired with its negative in , , which since is odd shows that , as required.
Dedekind's two proofs using Gaussian integers
Richard Dedekind
Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and
the axiomatic foundations of arithmetic. His ...
gave at least two proofs of Fermat's theorem on sums of two squares, both using the arithmetical properties of the Gaussian integers, which are numbers of the form ''a'' + ''bi'', where ''a'' and ''b'' are integers, and ''i'' is the square root of −1. One appears in section 27 of his exposition of ideals published in 1877; the second appeared in Supplement XI to
Peter Gustav Lejeune Dirichlet
Johann Peter Gustav Lejeune Dirichlet (; 13 February 1805 – 5 May 1859) was a German mathematician who made deep contributions to number theory (including creating the field of analytic number theory), and to the theory of Fourier series and ...
's ''
Vorlesungen über Zahlentheorie
(German for ''Lectures on Number Theory'') is the name of several different textbooks of number theory. The best known was written by Peter Gustav Lejeune Dirichlet and Richard Dedekind, and published in 1863. Others were written by Leopold Krone ...
'', and was published in 1894.
1. First proof. If is an odd
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), 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 ...
, then we have in the Gaussian integers. Consequently, writing a Gaussian integer ω = ''x'' + ''iy'' with ''x,y'' ∈ Z and applying the Frobenius automorphism in Z 'i''(''p''), one finds
:
since the automorphism fixes the elements of Z/(''p''). In the current case, for some integer n, and so in the above expression for ωp, the exponent (p-1)/2 of -1 is even. Hence the right hand side equals ω, so in this case the Frobenius endomorphism of Z 'i''(''p'') is the identity.
Kummer had already established that if is the
order
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of ...
of the Frobenius automorphism of Z 'i''(''p''), then the
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considered ...
prime ideal
In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together wi ...
s. (In fact, Kummer had established a much more general result for any extension of Z obtained by adjoining a primitive ''m''-th
root of unity
In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important i ...
, where ''m'' was any positive integer; this is the case of that result.) Therefore, the ideal (''p'') is the product of two different prime ideals in Z 'i'' Since the Gaussian integers are a
Euclidean domain
In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers ...
for the norm function , every ideal is principal and generated by a nonzero element of the ideal of minimal norm. Since the norm is multiplicative, the norm of a generator of one of the ideal factors of (''p'') must be a strict divisor of , so that we must have , which gives Fermat's theorem.
2. Second proof. This proof builds on Lagrange's result that if is a prime number, then there must be an integer ''m'' such that is divisible by ''p'' (we can also see this by
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then
:
a^ \equiv
\begin
\;\;\,1\pmod& \textx ...
); it also uses the fact that the Gaussian integers are a
unique factorization domain
In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
(because they are a Euclidean domain). Since does not divide either of the Gaussian integers and (as it does not divide their imaginary parts), but it does divide their product , it follows that cannot be a
prime
A prime number (or a prime) 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 ...
element in the Gaussian integers. We must therefore have a nontrivial factorization of ''p'' in the Gaussian integers, which in view of the norm can have only two factors (since the norm is multiplicative, and , there can only be up to two factors of p), so it must be of the form for some integers and . This immediately yields that .
Proof by Minkowski's Theorem
For congruent to mod a prime, is a
quadratic residue
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that:
:x^2\equiv q \pmod.
Otherwise, ''q'' is called a quadratic no ...
mod by
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then
:
a^ \equiv
\begin
\;\;\,1\pmod& \textx ...
. Therefore, there exists an integer such that divides . Let be the
standard basis
In mathematics, the standard basis (also called natural basis or canonical basis) of a coordinate vector space (such as \mathbb^n or \mathbb^n) is the set of vectors whose components are all zero, except one that equals 1. For example, in the ...
elements for the
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
and set and . Consider the lattice . If then . Thus divides for any .
The area of the fundamental parallelogram of the lattice is . The area of the open disk, , of radius centered around the origin is . Furthermore, is convex and symmetrical about the origin. Therefore, by Minkowski's theorem there exists a nonzero vector such that . Both and so . Hence is the sum of the squares of the components of .
Zagier's "one-sentence proof"
Let be prime, let denote the
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
s (with or without zero), and consider the finite set of triples of numbers.
Then has two involutions: an obvious one whose fixed points correspond to representations of as a sum of two squares, and a more complicated one,
:
which has exactly one fixed point . This proves that the cardinality of is odd. Hence, has also a fixed point with respect to the obvious involution.
This proof, due to Zagier, is a simplification of an earlier proof by
Heath-Brown
David Rodney "Roger" Heath-Brown FRS (born 12 October 1952), is a British mathematician working in the field of analytic number theory.
Education
He was an undergraduate and graduate student of Trinity College, Cambridge; his research supervis ...
, which in turn was inspired by a proof of Liouville. The technique of the proof is a combinatorial analogue of the topological principle that the
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological spac ...
s of a
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
with an involution and of its fixed-point set have the same parity and is reminiscent of the use of ''sign-reversing involutions'' in the proofs of combinatorial bijections.
This proof is equivalent to a geometric or "visual" proof using "windmill" figures, given by Alexander Spivak in 2006 and described in thi MathOverflow post and this Mathologer YouTube video .
Proof with partition theory
In 2016, A. David Christopher gave a partition-theoretic proof by considering partitions of the odd prime having exactly two sizes , each occurring exactly times, and by showing that at least one such partition exists if is congruent to 1 modulo 4.A. David Christopher, A partition-theoretic proof of Fermat's Two Squares Theorem", Discrete Mathematics, 339 (2016) 1410–1411.
Lagrange's four-square theorem
Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four.
p = a_0^2 + a_1^2 + a_2^2 + a_ ...
*
Landau–Ramanujan constant In mathematics and the field of number theory, the Landau–Ramanujan constant is the positive real number ''b'' that occurs in a theorem proved by Edmund Landau in 1908, stating that for large x, the number of positive integers below x that are ...
**Richard Dedekind, ''The theory of algebraic integers''.
* L. E. Dickson. ''
History of the Theory of Numbers
''History of the Theory of Numbers'' is a three-volume work by L. E. Dickson summarizing work in number theory up to about 1920. The style is unusual in that Dickson mostly just lists results by various authors, with little further discussion. ...
'' Vol. 2. Chelsea Publishing Co., New York 1920
* Harold M. Edwards, ''Fermat's Last Theorem. A genetic introduction to algebraic number theory''. Graduate Texts in Mathematics no. 50, Springer-Verlag, NY, 1977.
*C. F. Gauss, '' Disquisitiones Arithmeticae'' (English Edition). Transl. by Arthur A. Clarke. Springer-Verlag, 1986.
*
*D. R. Heath-Brown, ''Fermat's two squares theorem''. Invariant, 11 (1984) pp. 3–5.
*
John Stillwell
John Colin Stillwell (born 1942) is an Australian mathematician on the faculties of the University of San Francisco and Monash University.
Biography
He was born in Melbourne, Australia and lived there until he went to the Massachusetts Institu ...
, Introduction to ''Theory of Algebraic Integers'' by Richard Dedekind. Cambridge Mathematical Library, Cambridge University Press, 1996.
* Don Zagier, ''A one-sentence proof that every prime p ≡ 1 mod 4 is a sum of two squares''. Amer. Math. Monthly 97 (1990), no. 2, 144,