Fermat's theorem on sums of two squares

Fermat's theorem on sums of two squares For other theorems named after Pierre de Fermat, see Fermat's theorem.

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as: {displaystyle p=x^{2}+^{2},} with x and y integers, se e apenas se {displaystyle pequiv 1{pmod {4}}.} The prime numbers for which this is true are called Pythagorean primes. Por exemplo, the primes 5, 13, 17, 29, 37 e 41 are all congruent to 1 módulo 4, and they can be expressed as sums of two squares in the following ways: {displaystyle 5=1^{2}+2^{2},quad 13=2^{2}+3^{2},quad 17=1^{2}+4^{2},quad 29=2^{2}+5^{2},quad 37=1^{2}+6^{2},quad 41=4^{2}+5^{2}.} Por outro lado, the primes 3, 7, 11, 19, 23 e 31 are all congruent to 3 módulo 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 ou 1 módulo 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 módulo 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.

Conteúdo 1 História 2 Gaussian primes 3 Resultados relacionados 4 Algorithm 4.1 Description 4.2 Exemplo 5 Provas 5.1 Euler's proof by infinite descent 5.2 Lagrange's proof through quadratic forms 5.3 Dedekind's two proofs using Gaussian integers 5.4 Proof by Minkowski's Theorem 5.5 Zagier's "one-sentence proof" 5.6 Proof with partition theory 6 Veja também 7 Referências 8 Notas 9 External links History Albert Girard 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.[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.

Gaussian primes Fermat's theorem on sums of two squares is strongly related with the theory of Gaussian primes.

A Gaussian integer is a complex number {displaystyle a+ib} such that a and b are integers. The norm {estilo de exibição N(a+ib)=a^{2}+b^{2}} 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 {displaystyle p=4k+3,} and that the second case occurs when {displaystyle p=4k+1} e {displaystyle p=2.} The last case is not considered in Fermat's statement, but is trivial, Como {displaystyle 2=1^{2}+1^{2}=N(1+eu).} Related results Above point of view on Fermat's theorem is a special case of the theory of factorization of ideals in rings of quadratic integers. Resumindo, E se {estilo de exibição {matemática {O}}_{quadrado {d}}} 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 {estilo de exibição {matemática {O}}_{quadrado {d}},} or the ideal norm of an ideal of {estilo de exibição {matemática {O}}_{quadrado {d}},} which is necessarily prime. Além disso, the law of quadratic reciprocity allows distinguishing the two cases in terms of congruences. Se {estilo de exibição {matemática {O}}_{quadrado {d}}} é um domínio de ideal principal, then p is an ideal norm if and only {displaystyle 4p=a^{2}-db^{2},} 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 {displaystyle d=-2} e {displaystyle d=-3.} If p is an odd prime, então {displaystyle p=x^{2}+2^{2}iff pequiv 1{mbox{ ou }}pequiv 3{pmod {8}},} {displaystyle p=x^{2}+3^{2}iff pequiv 1{pmod {3}}.} Fermat wrote also: If two primes which end in 3 ou 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.

Em outras palavras, if p, q are of the form 20k + 3 or 20k + 7, then pq = x2 + 5ano 2. Euler later extended this to the conjecture that {displaystyle p=x^{2}+5^{2}iff pequiv 1{mbox{ ou }}pequiv 9{pmod {20}},} {displaystyle 2p=x^{2}+5^{2}iff pequiv 3{mbox{ ou }}pequiv 7{pmod {20}}.} Both Fermat's assertion and Euler's conjecture were established by Joseph-Louis Lagrange. This more complicate formulation relies on the fact that {estilo de exibição {matemática {O}}_{quadrado {-5}}} is not a principal ideal domain, contrarily to {estilo de exibição {matemática {O}}_{quadrado {-2}}} e {estilo de exibição {matemática {O}}_{quadrado {-3}}.} Algorithm There is a trivial algorithm for decomposing a prime of the form {displaystyle p=4k+1} into a sum of two squares: For all n such {displaystyle 1leq n<{sqrt {p}}} , test whether the square root of {displaystyle p-n^{2}} is an integer. If this the case, one has got the decomposition. However the input size of the algorithm is {displaystyle log p,} 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 {displaystyle {sqrt {p}}=exp left({frac {log p}{2}}right),} and thus exponential in the input size. So the computational complexity of this algorithm is exponential. 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).[5] Description Given an odd prime {displaystyle p} in the form {displaystyle 4k+1} , first find {displaystyle x} such that {displaystyle x^{2}equiv -1{pmod {p}}} . This can be done by finding a Quadratic non-residue modulo {displaystyle p} , say {displaystyle q} , and letting {displaystyle x=q^{frac {p-1}{4}}{pmod {p}}} . Such an {displaystyle x} will satisfy the condition since quadratic non-residues satisfy {displaystyle q^{frac {p-1}{2}}equiv -1{pmod {p}}} . Once {displaystyle x} is determined, one can apply the Euclidean algorithm with {displaystyle p} and {displaystyle x} . Denote the first two remainders that are less than the square root of {displaystyle p} as {displaystyle a} and {displaystyle b} . Then it will be the case that {displaystyle a^{2}+b^{2}=p} . Example Take {displaystyle p=97} . A possible quadratic non-residue for 97 is 13, since {displaystyle 13^{frac {97-1}{2}}equiv -1{pmod {97}}} . so we let {displaystyle x=13^{frac {97-1}{4}}=22{pmod {97}}} . The Euclidean algorithm applied to 97 and 22 yields: {displaystyle 97=22(4)+9,} {displaystyle 22=9(2)+4,} {displaystyle 9=4(2)+1,} {displaystyle 4=1(4).} The first two remainders smaller than the square root of 97 are 9 and 4; and indeed we have {displaystyle 97=9^{2}+4^{2}} , 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 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's proof by infinite descent 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. This is a well-known property, based on the identity {displaystyle (a^{2}+b^{2})(p^{2}+q^{2})=(ap+bq)^{2}+(aq-bp)^{2}} due to Diophantus. 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 {displaystyle a^{2}+b^{2}} is divisible by {displaystyle p^{2}+q^{2}} and that this latter is a prime. Then {displaystyle p^{2}+q^{2}} divides {displaystyle (pb-aq)(pb+aq)=p^{2}b^{2}-a^{2}q^{2}=p^{2}(a^{2}+b^{2})-a^{2}(p^{2}+q^{2}).} Since {displaystyle p^{2}+q^{2}} is a prime, it divides one of the two factors. Suppose that it divides {displaystyle pb-aq} . Since {displaystyle (a^{2}+b^{2})(p^{2}+q^{2})=(ap+bq)^{2}+(aq-bp)^{2}} (Diophantus's identity) it follows that {displaystyle p^{2}+q^{2}} must divide {displaystyle (ap+bq)^{2}} . So the equation can be divided by the square of {displaystyle p^{2}+q^{2}} . Dividing the expression by {displaystyle (p^{2}+q^{2})^{2}} yields: {displaystyle {frac {a^{2}+b^{2}}{p^{2}+q^{2}}}=left({frac {ap+bq}{p^{2}+q^{2}}}right)^{2}+left({frac {aq-bp}{p^{2}+q^{2}}}right)^{2}} and thus expresses the quotient as a sum of two squares, as claimed. On the other hand if {displaystyle p^{2}+q^{2}} divides {displaystyle pb+aq} , a similar argument holds by using the following variant of Diophantus's identity: {displaystyle (a^{2}+b^{2})(q^{2}+p^{2})=(aq+bp)^{2}+(ap-bq)^{2}.} 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 {displaystyle q} is a number not expressible as a sum of two squares, which divides {displaystyle a^{2}+b^{2}} . Write the quotient, factored into its (possibly repeated) prime factors, as {displaystyle p_{1}p_{2}cdots p_{n}} so that {displaystyle a^{2}+b^{2}=qp_{1}p_{2}cdots p_{n}} . If all factors {displaystyle p_{i}} can be written as sums of two squares, then we can divide {displaystyle a^{2}+b^{2}} successively by {displaystyle p_{1}} , {displaystyle p_{2}} , 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 {displaystyle q} then {displaystyle q} itself would have to be equal to the sum of two squares, which is a contradiction. So at least one of the primes {displaystyle p_{i}} is not the sum of two squares. 4. If {displaystyle a} and {displaystyle b} are relatively prime positive integers then every factor of {displaystyle a^{2}+b^{2}} 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 {displaystyle a,b} be relatively prime positive integers: without loss of generality {displaystyle a^{2}+b^{2}} is not itself prime, otherwise there is nothing to prove. Let {displaystyle q} therefore be a proper factor of {displaystyle a^{2}+b^{2}} , not necessarily prime: we wish to show that {displaystyle q} is a sum of two squares. Again, we lose nothing by assuming {displaystyle q>2} since the case {displaystyle q=2=1^{2}+1^{2}} is obvious. Deixar {estilo de exibição m,n} be non-negative integers such that {displaystyle mq,nq} are the closest multiples of {estilo de exibição q} (in absolute value) para {estilo de exibição a,b} respectivamente. Notice that the differences {displaystyle c=a-mq} e {displaystyle d=b-nq} are integers of absolute value strictly less than {displaystyle q/2} : na verdade, quando {displaystyle q>2} é par, mdc {estilo de exibição (uma,q/2)=1} ; otherwise since gcd {estilo de exibição (uma,q/2)mid q/2mid qmid a^{2}+b^{2}} , we would also have gcd {estilo de exibição (uma,q/2)mid b} . Multiplying out we obtain {estilo de exibição a^{2}+b^{2}=m^{2}q^{2}+2mqc+c^{2}+n^{2}q^{2}+2nqd+d^{2}=Aq+(c^{2}+d^{2})} uniquely defining a non-negative integer {estilo de exibição A} . Desde {estilo de exibição q} divides both ends of this equation sequence it follows that {displaystyle c^{2}+d^{2}} must also be divisible by {estilo de exibição q} : dizer {displaystyle c^{2}+d^{2}=qr} . Deixar {estilo de exibição g} be the gcd of {estilo de exibição c} e {estilo de exibição d} which by the co-primeness of {estilo de exibição a,b} is relatively prime to {estilo de exibição q} . Desta forma {estilo de exibição g^{2}} divides {estilo de exibição r} , so writing {displaystyle e=c/g} , {displaystyle f=d/g} e {displaystyle s=r/g^{2}} , we obtain the expression {estilo de exibição e^{2}+f^{2}=qs} for relatively prime {estilo de exibição e} e {estilo de exibição f} , e com {estilo de exibição s2yend{casos}}} which has exactly one fixed point {estilo de exibição (1,1,k)} . This proves that the cardinality of {estilo de exibição S} é estranho. Por isso, {estilo de exibição S} 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 and this Mathologer YouTube video Why was this visual proof missed for 400 anos? (Fermat's two square theorem) on YouTube.

Proof with partition theory In 2016, UMA. David Christopher gave a partition-theoretic proof by considering partitions of the odd prime {estilo de exibição m} having exactly two sizes {estilo de exibição a_{eu}(i=1,2)} , each occurring exactly {estilo de exibição a_{eu}} vezes, and by showing that at least one such partition exists if {estilo de exibição m} é congruente com 1 módulo 4.[15] See also Legendre's three-square theorem Lagrange's four-square theorem Landau–Ramanujan constant Thue's lemma Friedlander–Iwaniec theorem References D. UMA. Cox (1989). Primes of the Form x2 + ny2. Wiley-Interscience. ISBN 0-471-50654-0.*Richard Dedekind, The theory of algebraic integers. eu. E. Dickson. History of the Theory of Numbers Vol. 2. Chelsea Publishing Co., Nova york 1920 Harold M. Edwards, Fermat's Last Theorem. A genetic introduction to algebraic number theory. Graduate Texts in Mathematics no. 50, Springer-Verlag, Nova Iorque, 1977. C. F. Gauss, Disquisitiones Arithmeticae (English Edition). Transl. by Arthur A. Clarke. Springer-Verlag, 1986. Goldman, Jay R. (1998), The Queen of Mathematics: A historically motivated guide to Number Theory, A K Peters, ISBN 1-56881-006-7 D. R. Heath-Brown, Fermat's two squares theorem. Invariant, 11 (1984) pp. 3-5. John Stillwell, Introduction to Theory of Algebraic Integers by Richard Dedekind. Cambridge Mathematical Library, Cambridge University Press, 1996. ISBN 0-521-56518-9 Don Zagier, A one-sentence proof that every prime p ≡ 1 mod 4 is a sum of two squares. América. Matemática. Por mês 97 (1990), não. 2, 144, doi:10.2307/2323918 Notes ^ For a proof of the converse see for instance 20.1, Teoremas 367 e 368, dentro: G.H. Hardy and E.M. Wright. An introduction to the theory of numbers, Oxford 1938. ^ Simon Stevin. l'Arithmétique de Simon Stevin de Bruges, annotated by Albert Girard, Leyde 1625, p. 622. ^ L. E. Dickson, History of the Theory of Numbers, Volume. II, CH. VI, p. 227. "UMA. Girard ... had already made a determination of the numbers expressible as a sum of two integral squares: every square, every prime 4n+1, a product formed of such numbers, and the double of the foregoing" ^ L. E. Dickson, History of the Theory of Numbers, Volume. II, CH. VI, p. 228. ^ Wagon, Stan (1990), "Editor's Corner: The Euclidean Algorithm Strikes Again", Mensal de Matemática Americana, 97 (2): 125, doi:10.2307/2323912, MR 1041889. ^ De numerus qui sunt aggregata quorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/3), 1758, 3-40) ^ Demonstratio theorematis FERMATIANI omnem numerum primum formae 4n+1 esse summam duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 5 (1754/5), 1760, 3-13) ^ Zagier, D. (1990), "A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares", Mensal de Matemática Americana, 97 (2): 144, doi:10.2307/2323918, MR 1041893. ^ A. David Christopher. "A partition-theoretic proof of Fermat's Two Squares Theorem", Matemática Discreta 339:4:1410–1411 (6 abril 2016) doi:10.1016/j.disc.2015.12.002 ^ Euler à Goldbach, lettre CXXV ^ De numerus qui sunt aggregata duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/3), 1758, 3-40) [1] ^ Demonstratio theorematis FERMATIANI omnem numerum primum formae 4n+1 esse summam duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 5 (1754/5), 1760, 3-13) [2] ^ The summary is based on Edwards book, Páginas 45-48. ^ Nouv. Eu tenho. Acad. Berlim, année 1771, 125; ibid. année 1773, 275; ibid année 1775, 351. ^ A. David Christopher, A partition-theoretic proof of Fermat's Two Squares Theorem", Matemática Discreta, 339 (2016) 1410–1411. External links Two more proofs at PlanetMath.org "A one-sentence proof of the theorem". Arquivado a partir do original em 5 Fevereiro 2012. Fermat's two squares theorem, D. R. Heath-Brown, 1984. hide vte Pierre de Fermat Work Fermat's Last TheoremFermat numberFermat's principleFermat's little theoremFermat polygonal number theoremFermat pseudoprimeFermat pointFermat's theorem (stationary points)Fermat's theorem on sums of two squaresFermat's spiralFermat's right triangle theorem Related List of things named after Pierre de FermatWiles's proof of Fermat's Last TheoremFermat's Last Theorem in fictionFermat PrizeFermat's Last Tango (2000 musical)Fermat's Last Theorem (popular science book) Categorias: Additive number theorySquares in number theoryTheorems in number theory