NationMaster - Encyclopedia: Proofs of Fermat's theorem on sums of two squares

This mathematics article is devoted entirely to providing mathematical proofs and support for claims and statements made in the article Fermat's theorem on sums of two squares. This article is currently an experimental vehicle to see how well we can provide proofs and details for a math article without cluttering up the main article itself. See Wikipedia:WikiProject Mathematics/Proofs for some current discussion. This article is "experimental" in the sense that it is a test of one way we may be able to incorporate more detailed proofs in Wikipedia.

Fermat's theorem on sums of two squares states that an odd prime $p$ can be expressed as Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true. ... In mathematics, Pierre de Fermats theorem on sums of two squares states that an odd prime number p is expressible as with x and y integers, if and only if For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and... In mathematics, Pierre de Fermats theorem on sums of two squares states that an odd prime number p is expressible as with x and y integers, if and only if For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and...

$p = x 2 + y 2$ with $x$ and $y$ integers if and only if $p equiv 1 pmod{4}.$ It was originally announced by Fermat in 1640, but he gave no proof. Pierre de Fermat Pierre de Fermat IPA: (August 17, 1601â€“January 12, 1665) was a French lawyer at the Parlement of Toulouse, France, and a mathematician who is given credit for early developments that led to modern calculus. ...

The only if clause is trivial: the squares modulo $4$ are $0$ and $1$ , so $x 2 + y 2$ is congruent to $0$ , $1$ , or $2$ modulo $4$ . Since $p$ is assumed to be odd, this means that it must be congruent to $1$ modulo $4.$ The word modulo (Latin, with respect to a modulus of ___) is the Latin ablative of modulus which itself means a small measure. ...

1 Euler's proof by infinite descent
2 Lagrange's proof through quadratic forms
3 Dedekind's proofs with Gaussian integers
4 References
5 External links

Euler's proof by infinite descent

Euler did not succeed in proving Fermat's theorem on sums of two squares, when he was forty years old. He communicated this in a letter to Goldbach dated 6 May 1747. The proof relies on infinite descent, and proceeds in five steps; the fifth step below is from another letter to Goldbach written in 1749, as the first letter was vague on that final step: Leonhard Euler aged 49 (oil painting by Emanuel Handmann, 1756) Leonhard Euler (April 15, 1707 - September 18, 1783) (pronounced oiler) was a Swiss mathematician and physicist. ... Christian Goldbach (March 18, 1690 - November 20, 1764), was a Prussian mathematician, who was born in Königsberg, Prussia, as son of a pastor. ... May 6 is the 126th day of the year in the Gregorian calendar (127th in leap years). ... Year 1747 (MDCCXLVII) was a common year starting on Sunday (link will display the full calendar) of the Gregorian calendar (or a common year starting on Thursday of the 11-day slower Julian calendar). ... Events While in debtors prison, John Cleland writes Fanny Hill (Memoirs of a Woman of Pleasure). ...

1. The product of two numbers, each of which is a sum of two squares, is itself a sum of two squares.

This is simply a restatement of the Brahmagupta-Fibonacci identity.

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. In algebra, Brahmaguptas identity, also sometimes called Fibonaccis identity, says that the product of two numbers, each of which is a sum of two squares, is itself a sum of two squares (and in two different ways). ...

Indeed, suppose for example that

a 2 + b 2

is divisible by

p 2 + q 2

and that this latter is a prime. Then

p 2 + q 2

divides

(p b - a q)(p b + a q) = p 2 b 2 - a 2 q 2 = p 2 (a 2 + b 2) - a 2 (p 2 + q 2).

Since

p 2 + q 2

is a prime, it divides one of the two factors. Suppose that it divides

p b - a q

. Since

$(a^2+b^2)(p^2+q^2) = (ap+bq)^2 + (aq-bp)^2,$

(Brahmagupta-Fibonacci identity) it follows that

p 2 + q 2

must divide

(a p + b q) 2

. So the equation can be divided by the square of

p 2 + q 2

. Dividing the expression by

(p 2 + q 2) 2

yields:

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

p 2 + q 2

divides

p b + a q

, a similar argument holds by using

$(a^2+b^2)(q^2+p^2) = (aq+bp)^2 + (ap-bq)^2,$

(Brahmagupta-Fibonacci 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. In algebra, Brahmaguptas identity, also sometimes called Fibonaccis identity, says that the product of two numbers, each of which is a sum of two squares, is itself a sum of two squares (and in two different ways). ... In algebra, Brahmaguptas identity, also sometimes called Fibonaccis identity, says that the product of two numbers, each of which is a sum of two squares, is itself a sum of two squares (and in two different ways). ...

Suppose

x

divides

a 2 + b 2

and that the quotient, factored into its prime factors is $p_1p_2cdots p_n$ . Then $a^2+b^2 = x p_1p_2cdots p_n$ . If all factors

p i

can be written as sums of two squares, then we can divide

a 2 + b 2

successively by

p 1

p 2

, etc., and applying the previous step we deduce that each quotient is a sum of two squares. This until we get to

x

, concluding that

x

would have to be the sum of two squares. So, by contrapositive, if

x

is not the sum of two squares, then at least one of the primes

p i

is not the sum of two squares.

4. If $a$ and $b$ are relatively prime then every factor of $a 2 + b 2$ is a sum of two squares.

This is the step that uses infinite descent. Let

x

be a factor of

a 2 + b 2

. We can write

$a = mx pm c,qquad b = nx pm d$

where

c

and

d

are at most half of

x

in absolute value. This gives:

$a^2 + b^2 = m^2x^2pm 2mxc + c^2 + n^2x^2 pm 2nxd + d^2 = Ax + (c^2+d^2).$

Therefore,

c 2 + d 2

must be divisible by

x

, say

c 2 + d 2 = y x

. If

c

and

d

are not relatively prime, then their gcd cannot divide

x

(if it did, then it would divide

a

and

b

which we assume are relatively prime). Thus the square of the gcd divides

y

(as it divides

c 2 + d 2

), giving us an expression of the form

e 2 + f 2 = z x

for relatively prime

e

and

f

, and with

z

no more than half of

x

, since

$zx = e^2 + f^2 leq c^2+d^2 leq left(frac{x}{2}right)^2 + left(frac{x}{2}right)^2 = frac{1}{2}x^2.$

c

and

d

are relatively prime, then we can use them directly instead of switching to

e

and

f

x

is not the sum of two squares, then by the third step there must be a factor of

z

which is not the sum of two squares; call it

w

. This gives an infinite descent, going from

x

to a smaller number

w

, both not the sums of two squares but dividing a sum of two squares. Since an infinite descent is impossible, we conclude that

x

must be expressible as a sum of two squares, as claimed.

5. Every prime of the form $4 n + 1$ is a sum of two squares.

p = 4 n + 1

, then by Fermat's Little Theorem each of the numbers $1, 2^{4n}, 3^{4n},dots, (4n)^{4n}$ is congruent to one modulo

p

. The differences $2^{4n}-1, 3^{4n}-2^{4n},dots,(4n)^{4n}-(4n-1)^{4n}$ are therefore all divisible by

p

. Each of these differences can be factored as

$a^{4n}-b^{4n} = left(a^{2n}+b^{2n}right)left(a^{2n}-b^{2n}right).$

Since

p

is prime, it must divide one of the two factors. If in any of the

4 n - 1

cases it divides the first factor, then by the previous step we conclude that

p

is itself a sum of two squares (since

a

and

b

differ by

1

, they are relatively prime). So it is enough to show that

p

cannot always divide the second factor. If it divides all

4 n - 1

differences $2^{2n}-1, 3^{2n}-2^{2n},dots,(4n)^{2n}-(4n-1)^{2n}$ , then it would divide all

4 n - 2

differences of successive terms, all

4 n - 3

differences of the differences, and so forth. Since the

k

th differences of the sequence $1^k, 2^k, 3^k,dots$ are all equal to

k!

, the

2 n

th differences would all be constant and equal to

(2 n)!

, which is certainly not divisible by

p

. Therefore,

p

cannot divide all the second factors which proves that

p

is indeed the sum of two squares.

Which of course was all wrong. Fermats little theorem (not to be confused with Fermats last theorem) states that if p is a prime number, then for any integer a, This means that if you start with a number, initialized to 1, and repeatedly multiply, for a total of p multiplications, that number by...

Lagrange's proof through quadratic forms

Lagrange gave a proof in 1770 based on his general theory of integral quadratic forms. The following is a slight simplification of his argument, due to Gauss, which appears in article 182 of the Disquisitiones Arithmeticae. Joseph-Louis Lagrange, comte de lEmpire (January 25, 1736 â€“ April 10, 1813; b. ... In mathematics, a quadratic form is a homogeneous polynomial of degree two in a number of variables. ... Carl Friedrich Gauss was a German mathematician and physicist. ... The Disquisitiones Arithmeticae is a textbook of number theory written by German mathematician Carl Friedrich Gauss and first published in 1801 when Gauss was 24. ...

A (binary) quadratic form will be taken to be an expression of the form $a x 2 + 2 b x y + c y 2$ with $a, b, c$ integers. A number $n$ is said to be represented by the form if there exist integers $x, y$ such that $n = a x 2 + 2 b x y + c y 2$ . Fermat's theorem on sums of two squares is then equivalent to the statement that a prime $p$ is represented by the form $x 2 + y 2$ (i.e., $a = c = 1$ , $b = 0$ ) exactly when $p$ is congruent to $1$ modulo $4$ .

The discriminant of the quadratic form is defined to be $b 2 - a c$ (this is the definition due to Gauss; Lagrange did not require the $x y$ term to have even coefficient, and defined the discriminant as $b 2 - 4 a c$ ). The discriminant of $x 2 + y 2$ is then equal to $- 1$ . In algebra, the discriminant of a polynomial is a certain expression in the coefficients of the polynomial which equals zero if and only if the polynomial has multiple roots in the complex numbers. ...

Two forms $a x 2 + 2 b x y + c y 2$ and $r x' 2 + 2 s x' y' + t y' 2$ are equivalent if and only if there exist substitutions with integer coefficients

x = α x' + β y'

y = γ x' + δ y'

with such that, when substituted into the first form, yield the second. Equivalent forms are readily seen to have the same discriminant. Moreover, it is clear that equivalent forms will represent exactly the same integers.

Lagrange proved that all forms of discriminant $- 1$ are equivalent. Thus, to prove Fermat's theorem it is enough to find any form of discriminant $- 1$ that represents $p$ . To do this, it suffices to find an integer $m$ such that $p$ divides $m 2 + 1$ . For, finding such an integer, we can consider the form

which has discriminant $- 1$ and represents $p$ by setting $x = 1$ and $y = 0$ .

Suppose then that $p = 4 n + 1$ . Again we invoke Fermat's Little Theorem: for any $z$ relatively prime to $p$ , we know that $p$ divides $z p - 1 - 1 = z 4 n - 1 = (z 2 n - 1)(z 2 n + 1)$ . Moreover, by a theorem of Lagrange, the number of solutions modulo $p$ to a congruence of degree $q$ modulo $p$ is at most $q$ (this follows since the integers modulo $p$ form a field, and a polynomial of degree $q$ has at most $q$ roots). So the congruence has at most $2 n$ solutions among the numbers . Therefore, there exists some positive integer $z$ strictly smaller than $p$ (and so relatively prime to $p$ ) such that $p$ does not divide $z 2 n - 1$ . Since $p$ divides $z 4 n - 1 = (z 2 n - 1)(z 2 n + 1)$ , $p$ must divide $z 2 n + 1$ . Setting $m = z n$ completes the proof.

Dedekind's proofs with Gaussian integers

Dedekind gave at least two proofs of Fermat's theorem on sums of two squares, both using the arithmetical properties of the Gaussian integers. One appears in section 27 of his exposition of ideals published in 1877; the second appeared in Supplement XI to Dirichlet's Lectures on Number Theory, and was published in 1894. Julius Wilhelm Richard Dedekind (October 6, 1831 - February 12, 1916) was a German mathematician and Ernst Eduard Kummers closest follower in arithmetic. ... A Gaussian integer is a complex number whose real and imaginary part are both integers. ... 1877 (MDCCCLXXVII) was a common year starting on Monday (see link for calendar). ... Johann Peter Gustav Lejeune Dirichlet (February 13, 1805 - May 5, 1859) was a German mathematician credited with the modern formal definition of a function. ... 1894 (MDCCCXCIV) was a common year starting on Monday (see link for calendar). ...

1. First proof. If $p$ is a positive odd rational prime, then we have , where $i$ is the imaginary square root of $- 1$ . Consequently, if $ω = x + i y$ is any Gaussian integer, then

If $p$ is congruent to $1$ modulo $4$ , then each Gaussian integer $ω$ satisfies the congruence

and therefore the ideal $(p)$ is the product of two different prime ideals of degree $1$ in Z[ $i$ ]. Since Z[ $i$ ] is a principal ideal domain, (in fact, a Euclidean domain), every ideal is principal, generated by an element of minimal norm. So if $α$ is a generator of one of the ideal factors of $(p)$ , then we must have $p = N (α) = N (a + b i) = a 2 + b 2$ which gives Fermat's theorem. In abstract algebra, a Euclidean domain (also called a Euclidean ring) is a type of ring in which the Euclidean algorithm can be used. ...

2. Second proof. This proof builds on Lagrange's result that if $p = 4 n + 1$ , then there must be a number of the form $m 2 + 1$ which is a multiple of $p$ . Since $p$ does not divide the Gaussian factors $m + i$ nor $m - i$ (the quotients are clearly equal to , which are not Gaussian integers), despite dividing the product, it follows that $p$ cannot be a prime in Z[ $i$ ]. Since it is not a prime, we must have a factorization in the Gaussian integers of the form $p = (x + y i)(x - y i)$ for some integers $x$ and $y$ , which immediately yields that $p = x 2 + y 2$ .

References

Richard Dedekind, The theory of algebraic integers.
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.
John Stillwell, Introduction to Theory of Algebraic Integers by Richard Dedekind. Cambridge Mathematical Library, Cambridge University Press, 1996.

The Disquisitiones Arithmeticae is a textbook of number theory written by German mathematician Carl Friedrich Gauss and first published in 1801 when Gauss was 24. ...

External links

Two more proofs at PlanetMath.org
A one-sentence proof of the theorem

Categories: Article proofs | Algebraic number theory | Quadratic forms

Results from FactBites:

Number theory - Wikipedia (545 words)
	Typical statements are Fermat's little theorem and Euler's theorem extending it, the Chinese remainder theorem and the law of quadratic reciprocity.
	Warings problem (representing a given integer as a sum of squares, cubes etc.), the Twin Prime Conjecture (finding infinitely many prime pairs with difference 2) and Goldbach's conjecture (writing even integers as sums of two primes) are being attacked with analytical methods as well.
	Proofs of the transcendence of mathematical constants, such as π or e, are also classified as analytical number theory.

NUMBER - LoveToKnow Article on NUMBER (10915 words)
	Thus the notions of one, two, and the vague many are fundamental, and must have impressed themselves on the human mind at a very early period: evidence of this is found in the grammatical distinction of singular, dual and plural which occurs in ancient languages of widely different races.
	Two numbers a, b are said to be congruent with respect to the modulus m, when (ab) is divisible by rn.
	In order that two forms may admit of composition into a third, it is necessary and sufficient that their determinants be in the ratio of two squares.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Euler's proof by infinite descent GA_googleFillSlot("encyclopedia_square");

Lagrange's proof through quadratic forms

Dedekind's proofs with Gaussian integers

References

External links

Euler's proof by infinite descent