In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:
with x and y integers, if and only if
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 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 (if number squared is even) or 1 (if number squared is odd) 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. [1] This generalization of Fermat's theorem is known as the sum of two squares theorem.
Albert Girard was the first to make the observation, characterizing the positive integers (not necessarily primes) that are expressible as the sum of two squares of positive integers; this was published in 1625. [2] [3] The statement that every prime p of the form 4n+1 is the sum of two squares is sometimes called Girard's theorem. [4] 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 dated December 25, 1640: for this reason this version of the theorem is sometimes called Fermat's Christmas theorem.
Fermat's theorem on sums of two squares is strongly related with the theory of Gaussian primes.
A Gaussian integer is a complex number such that a and b are integers. The norm of a Gaussian integer is an integer equal to the square of the absolute value 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. 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 1, −1, i and −i).
The multiplicative property of the norm implies that a prime number p 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
The above point of view on Fermat's theorem is a special case of the theory of factorization of ideals in rings of quadratic integers. In summary, if is the ring of algebraic integers in the quadratic field, then an odd prime number p, not dividing d, is either a prime element in or the ideal norm of an ideal of which is necessarily prime. Moreover, the law of quadratic reciprocity allows distinguishing the two cases in terms of congruences. If is a principal ideal domain, then p is an ideal norm if and only
with a and b both integers.
In a letter to Blaise Pascal dated September 25, 1654 Fermat announced the following two results that are essentially the special cases and If p is an odd prime, then
Fermat wrote also:
In other words, if p, q are of the form 20k + 3 or 20k + 7, then pq = x2 + 5y2. Euler later extended this to the conjecture that
Both Fermat's assertion and Euler's conjecture were established by Joseph-Louis Lagrange. This more complicated formulation relies on the fact that is not a principal ideal domain, unlike and
There is a trivial algorithm for decomposing a prime of the form into a sum of two squares: For all n such , test whether the square root of is an integer. If this is the case, one has got the decomposition.
However the input size of the algorithm is the number of digits of p (up to a constant factor that depends on the numeral base). The number of needed tests is of the order of and thus exponential in the input size. So the computational complexity of this algorithm is exponential.
A Las Vegas algorithm with a probabilistically polynomial complexity has been described by Stan Wagon in 1990, based on work by Serret and Hermite (1848), and Cornacchia (1908). [5] The probabilistic part consists in finding a quadratic non-residue, which can be done with success probability and then iterated if not successful. Conditionally this can also be done in deterministic polynomial time if the generalized Riemann hypothesis holds as explained for the Tonelli–Shanks algorithm.
Given an odd prime in the form , first find such that . This can be done by finding a quadratic non-residue modulo , say , and letting .
Such an will satisfy the condition since quadratic non-residues satisfy .
Once is determined, one can apply the Euclidean algorithm with and . Denote the first two remainders that are less than the square root of as and . Then it will be the case that .
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.
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 after much effort and is based on infinite descent. 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). [6] [7] Lagrange gave a proof in 1775 that was based on his study of quadratic 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 (who was inspired by Liouville's idea), Zagier presented a non-constructive one-sentence proof in 1990. [8] And more recently Christopher gave a partition-theoretic proof. [9]
Euler 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. [10] The proof relies on infinite descent, 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 [11] and do not correspond exactly to the four steps below. The fifth step below is from the second paper. [12] [13]
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.
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).
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).
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).
5. Every prime of the form is a sum of two squares. (This is the main result of Euler's second paper).
Lagrange completed a proof in 1775 [14] based on his general theory of integral quadratic forms. 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 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 = 2m 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 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 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.
Richard Dedekind 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's Vorlesungen über Zahlentheorie , and was published in 1894.
1. First proof. If p is an odd prime number, 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 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 f ∈ {1,2} is the order of the Frobenius automorphism of Z[i]/(p), then the ideal in Z[i] would be a product of 2/f distinct prime ideals. (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, where m was any positive integer; this is the case m = 4 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 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); it also uses the fact that the Gaussian integers are a unique factorization domain (because they are a Euclidean domain). Since p ∈ Z 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 p cannot be a prime 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 x and y. This immediately yields that .
For congruent to mod a prime, is a quadratic residue mod by Euler's criterion. Therefore, there exists an integer such that divides . Let be the standard basis elements for the vector space 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 .
Let be prime, let denote the natural numbers (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, 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 characteristics of a topological space 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 this MathOverflow post by Moritz Firsching and this YouTube video by Mathologer.
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. [15]
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.
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 number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as or
In number theory, Fermat's little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
In number theory, Euler's theorem states that, if n and a are coprime positive integers, then is congruent to modulo n, where denotes Euler's totient function; that is
This article collects together a variety of proofs of Fermat's little theorem, which states that
In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is, the factorial satisfies
Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as a sum of four non-negative integer squares. That is, the squares form an additive basis of order four. where the four numbers are integers. For illustration, 3, 31, and 310 in several ways, can be represented as the sum of four squares as follows:
In number theory, Dixon's factorization method is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by a polynomial.
In number theory, the von Staudt–Clausen theorem is a result determining the fractional part of Bernoulli numbers, found independently by Karl von Staudt and Thomas Clausen.
In mathematics, the Eisenstein integers, occasionally also known as Eulerian integers, are the complex numbers of the form
In algebraic number theory, the narrow class group of a number field K is a refinement of the class group of K that takes into account some information about embeddings of K into the field of real numbers.
A Pythagorean prime is a prime number of the form . Pythagorean primes are exactly the odd prime numbers that are the sum of two squares; this characterization is Fermat's theorem on sums of two squares.
In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusually large number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published.
Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x4 ≡ p is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the congruence x4 ≡ p to that of x4 ≡ q.
In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as
In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.
In logic, especially as applied in mathematics, concept A is a special case or specialization of concept B precisely if every instance of A is also an instance of B but not vice versa, or equivalently, if B is a generalization of A. A limiting case is a type of special case which is arrived at by taking some aspect of the concept to the extreme of what is permitted in the general case. If B is true, one can immediately deduce that A is true as well, and if B is false, A can also be immediately deduced to be false. A degenerate case is a special case which is in some way qualitatively different from almost all of the cases allowed.
In algebraic number theory Eisenstein's reciprocity law is a reciprocity law that extends the law of quadratic reciprocity and the cubic reciprocity law to residues of higher powers. It is one of the earliest and simplest of the higher reciprocity laws, and is a consequence of several later and stronger reciprocity laws such as the Artin reciprocity law. It was introduced by Eisenstein, though Jacobi had previously announced a similar result for the special cases of 5th, 8th and 12th powers in 1839.
{{cite web}}
: CS1 maint: unfit URL (link)