Prove That the Product of Two Integers of the Form 4n 1 Is Again of the Form 4n 1.

Condition under which an odd prime is a sum of two squares

For other theorems named afterwards Pierre de Fermat, see Fermat'south theorem.

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p tin exist expressed equally:

${\displaystyle p=x^{two}+y^{2},}$

with x and y integers, if and only if

${\displaystyle p\equiv 1{\pmod {iv}}.}$

The prime numbers for which this is true are chosen Pythagorean primes. For example, the primes five, 13, 17, 29, 37 and 41 are all congruent to one modulo 4, and they tin be expressed as sums of ii squares in the following means:

${\displaystyle five=1^{2}+2^{two},\quad 13=2^{two}+3^{two},\quad 17=i^{2}+iv^{2},\quad 29=2^{two}+v^{2},\quad 37=1^{2}+six^{2},\quad 41=4^{2}+five^{2}.}$

On the other hand, the primes three, 7, eleven, nineteen, 23 and 31 are all congruent to 3 modulo 4, and none of them tin be expressed as the sum of ii squares. This is the easier part of the theorem, and follows immediately from the ascertainment that all squares are coinciding to 0 or ane modulo 4.

Since the Diophantus identity implies that the product of two integers each of which can be written equally the sum of two squares is itself expressible every bit the sum of 2 squares, by applying Fermat'due south theorem to the prime number factorization of any positive integer north, nosotros see that if all the prime factors of n congruent to 3 modulo 4 occur to an even exponent, and so n is expressible equally a sum of 2 squares. The converse also holds.^[one] This generalization of Fermat's theorem is known equally the sum of two squares theorem.

History [edit]

Albert Girard was the get-go to make the observation, describing all positive integer numbers (not necessarily primes) expressible equally 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 role, 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 ii squares) in a letter of the alphabet to Marin Mersenne dated Dec 25, 1640: for this reason this version of the theorem is sometimes chosen Fermat's Christmas theorem.

Gaussian primes [edit]

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

A Gaussian integer is a circuitous number ${\displaystyle a+ib}$ such that a and b are integers. The norm ${\displaystyle North(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 production of Gaussian integers is the product of their norm. This is Diophantus identity, which results immediately from the like property of the absolute value.

Gaussian integers grade a primary ideal domain. This implies that Gaussian primes can be defined similarly every bit primes numbers, that is as those Gaussian integers that are not the product of 2 non-units (hither the units are 1, −1, i and −i ).

The multiplicative belongings 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 showtime instance occurs when ${\displaystyle p=4k+iii,}$ and that the second instance occurs when ${\displaystyle p=4k+1}$ and ${\displaystyle p=ii.}$ The last case is non considered in Fermat's argument, but is trivial, as ${\displaystyle 2=ane^{2}+1^{two}=N(1+i).}$

[edit]

In a higher place indicate 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 ${\displaystyle {\mathcal {O}}_{\sqrt {d}}}$ is the ring of algebraic integers in the quadratic field, and so an odd prime number p, not dividing d, is either a prime chemical element in ${\displaystyle {\mathcal {O}}_{\sqrt {d}},}$ or the ideal norm of an ideal of ${\displaystyle {\mathcal {O}}_{\sqrt {d}},}$ which is necessarily prime number. Moreover, the law of quadratic reciprocity allows distinguishing the two cases in terms of congruences. If ${\displaystyle {\mathcal {O}}_{\sqrt {d}}}$ is a chief ideal domain, 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 post-obit two results that are essentially the special cases ${\displaystyle d=-2}$ and ${\displaystyle d=-3.}$ If p is an odd prime number, and so

${\displaystyle p=10^{2}+2y^{two}\iff p\equiv 1{\mbox{ or }}p\equiv 3{\pmod {8}},}$

${\displaystyle p=x^{two}+3y^{2}\iff p\equiv 1{\pmod {iii}}.}$

Fermat wrote also:

If 2 primes which terminate in 3 or 7 and surpass by three a multiple of four are multiplied, then their product will be composed of a square and the quintuple of another square.

In other words, if p, q are of the course 20k + 3 or 201000 + 7, then pq = 10 ² + vy ^two . Euler later extended this to the theorize that

${\displaystyle p=x^{2}+5y^{2}\iff p\equiv 1{\mbox{ or }}p\equiv 9{\pmod {20}},}$

${\displaystyle 2p=10^{2}+5y^{2}\iff p\equiv 3{\mbox{ or }}p\equiv 7{\pmod {20}}.}$

Both Fermat's exclamation and Euler'southward conjecture were established by Joseph-Louis Lagrange. This more complicate conception relies on the fact that ${\displaystyle {\mathcal {O}}_{\sqrt {-five}}}$ is non a master ideal domain, contrarily to ${\displaystyle {\mathcal {O}}_{\sqrt {-2}}}$ and ${\displaystyle {\mathcal {O}}_{\sqrt {-iii}}.}$

Algorithm [edit]

There is a petty algorithm for decomposing a prime of the form ${\displaystyle p=4k+1}$ into a sum of ii squares: For all due north such ${\displaystyle 1\leq n<{\sqrt {p}}}$ , exam whether the square root of ${\displaystyle p-north^{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 gene 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}}\correct),}$ and thus exponential in the input size. Then the computational complexity of this algorithm is exponential.

An algorithm with a polynomial complexity has been described past Stan Wagon in 1990, based on piece of work past Serret and Hermite (1848), and Cornacchia (1908).^[five]

Description [edit]

Given an odd prime ${\displaystyle p}$ in the form ${\displaystyle 4k+1}$ , first find ${\displaystyle x}$ such that ${\displaystyle 10^{two}\equiv -1{\pmod {p}}}$ . This tin can be done by finding a Quadratic not-rest modulo ${\displaystyle p}$ , say ${\displaystyle q}$ , and letting ${\displaystyle x=q^{\frac {p-one}{4}}{\pmod {p}}}$ .

Such an ${\displaystyle x}$ will satisfy the condition since quadratic non-residues satisfy ${\displaystyle q^{\frac {p-1}{ii}}\equiv -1{\pmod {p}}}$ .

Once ${\displaystyle ten}$ is determined, one can use the Euclidean algorithm with ${\displaystyle p}$ and ${\displaystyle x}$ . Denote the commencement two remainders that are less than the square root of ${\displaystyle p}$ as ${\displaystyle a}$ and ${\displaystyle b}$ . So it will be the case that ${\displaystyle a^{ii}+b^{2}=p}$ .

Example [edit]

Take ${\displaystyle p=97}$ . A possible quadratic non-residue for 97 is thirteen, since ${\displaystyle 13^{\frac {97-1}{2}}\equiv -1{\pmod {97}}}$ . and then we let ${\displaystyle x=xiii^{\frac {97-1}{4}}=22{\pmod {97}}}$ . The Euclidean algorithm practical to 97 and 22 yields:

$${\displaystyle 97=22(iv)+9,}$$

$${\displaystyle 22=nine(2)+four,}$$

$${\displaystyle ix=4(2)+i,}$$

$${\displaystyle 4=i(4).}$$

The first 2 remainders smaller than the square root of 97 are 9 and iv; and indeed nosotros have ${\displaystyle 97=9^{two}+4^{2}}$ , every bit expected.

Proofs [edit]

Fermat usually did not write down proofs of his claims, and he did not provide a proof of this statement. The first proof was plant past Euler later on much endeavor and is based on infinite descent. He announced information technology in two messages to Goldbach, on May 6, 1747 and on Apr 12, 1749; he published the detailed proof in two manufactures (between 1752 and 1755).^{[6] [7]} Lagrange gave a proof in 1775 that was based on his written report of quadratic forms. This proof was simplified by Gauss in his Disquisitiones Arithmeticae (fine art. 182). Dedekind gave at least two proofs based on the arithmetic of the Gaussian integers. In that location is an elegant proof using Minkowski'due south theorem nearly convex sets. Simplifying an earlier curt 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 [edit]

Euler succeeded in proving Fermat's theorem on sums of two squares in 1749, when he was forty-2 years quondam. He communicated this in a letter of the alphabet to Goldbach dated 12 April 1749.^[10] The proof relies on infinite descent, and is simply briefly sketched in the letter. The total proof consists in 5 steps and is published in two papers. The beginning four steps are Propositions 1 to iv of the first paper^[11] and do non represent exactly to the four steps below. The fifth step below is from the 2nd paper.^{[12] [thirteen]}

For the avoidance of ambiguity, zero will always be a valid possible constituent of "sums of two squares", then for example every square of an integer is trivially expressible as the sum of two squares by setting one of them to exist zero.

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

This is a well-known belongings, based on the identity

${\displaystyle (a^{2}+b^{2})(p^{two}+q^{2})=(ap+bq)^{2}+(aq-bp)^{ii}}$

due to Diophantus.

2. If a number which is a sum of two squares is divisible past a prime which is a sum of ii squares, then the caliber is a sum of ii squares. (This is Euler'southward first Proposition).

Indeed, suppose for example that ${\displaystyle a^{2}+b^{two}}$ 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^{ii}b^{2}-a^{two}q^{2}=p^{2}(a^{2}+b^{ii})-a^{2}(p^{2}+q^{2}).}$

Since ${\displaystyle p^{2}+q^{2}}$ is a prime number, information technology divides one of the two factors. Suppose that it divides ${\displaystyle pb-aq}$ . Since

${\displaystyle (a^{ii}+b^{2})(p^{2}+q^{2})=(ap+bq)^{two}+(aq-bp)^{2}}$

(Diophantus's identity) it follows that ${\displaystyle p^{2}+q^{ii}}$ must divide ${\displaystyle (ap+bq)^{2}}$ . So the equation can exist divided by the square of ${\displaystyle p^{2}+q^{2}}$ . Dividing the expression by ${\displaystyle (p^{2}+q^{2})^{two}}$ yields:

${\displaystyle {\frac {a^{2}+b^{ii}}{p^{two}+q^{2}}}=\left({\frac {ap+bq}{p^{2}+q^{2}}}\right)^{2}+\left({\frac {aq-bp}{p^{2}+q^{ii}}}\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 past using the following variant of Diophantus's identity:

${\displaystyle (a^{2}+b^{2})(q^{two}+p^{2})=(aq+bp)^{2}+(ap-bq)^{ii}.}$

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 ii squares, then the quotient has a factor which is not a sum of ii squares. (This is Euler's second Proffer).

Suppose ${\displaystyle q}$ is a number non expressible equally a sum of two squares, which divides ${\displaystyle a^{2}+b^{ii}}$ . Write the caliber, factored into its (mayhap repeated) prime number factors, every bit ${\displaystyle p_{1}p_{2}\cdots p_{north}}$ then that ${\displaystyle a^{2}+b^{two}=qp_{1}p_{2}\cdots p_{n}}$ . If all factors ${\displaystyle p_{i}}$ tin exist written as sums of two squares, then we can carve up ${\displaystyle a^{2}+b^{2}}$ successively by ${\displaystyle p_{1}}$ , ${\displaystyle p_{2}}$ , etc., and applying step (2.) higher up we deduce that each successive, smaller, caliber is a sum of two squares. If we get all the style downwards to ${\displaystyle q}$ and so ${\displaystyle q}$ itself would have to be equal to the sum of two squares, which is a contradiction. So at to the lowest degree one of the primes ${\displaystyle p_{i}}$ is not the sum of ii squares.

4. If ${\displaystyle a}$ and ${\displaystyle b}$ are relatively prime positive integers and so every gene of ${\displaystyle a^{2}+b^{two}}$ is a sum of two squares. (This is the step that uses pace (3.) to produce an 'space descent' and was Euler'south Proposition 4. The proof sketched beneath likewise includes the proof of his Proposition iii).

Permit ${\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. Permit ${\displaystyle q}$ therefore be a proper factor of ${\displaystyle a^{2}+b^{2}}$ , not necessarily prime: we wish to testify that ${\displaystyle q}$ is a sum of two squares. Once more, we lose nothing past assuming ${\displaystyle q>2}$ since the example ${\displaystyle q=2=one^{2}+1^{2}}$ is obvious.

Let ${\displaystyle 1000,northward}$ be non-negative integers such that ${\displaystyle mq,nq}$ are the closest multiples of ${\displaystyle q}$ (in absolute value) to ${\displaystyle a,b}$ respectively. Notice that the differences ${\displaystyle c=a-mq}$ and ${\displaystyle d=b-nq}$ are integers of accented value strictly less than ${\displaystyle q/two}$ : indeed, when ${\displaystyle q>two}$ is even, gcd ${\displaystyle (a,q/2)=one}$ ; otherwise since gcd ${\displaystyle (a,q/two)\mid q/2\mid q\mid a^{two}+b^{ii}}$ , we would also have gcd ${\displaystyle (a,q/2)\mid b}$ .

Multiplying out nosotros obtain

${\displaystyle a^{2}+b^{two}=m^{2}q^{2}+2mqc+c^{two}+north^{2}q^{2}+2nqd+d^{2}=Aq+(c^{two}+d^{ii})}$

uniquely defining a non-negative integer ${\displaystyle A}$ . Since ${\displaystyle q}$ divides both ends of this equation sequence it follows that ${\displaystyle c^{two}+d^{2}}$ must as well be divisible by ${\displaystyle q}$ : say ${\displaystyle c^{ii}+d^{ii}=qr}$ . Let ${\displaystyle chiliad}$ be the gcd of ${\displaystyle c}$ and ${\displaystyle d}$ which by the co-primeness of ${\displaystyle a,b}$ is relatively prime to ${\displaystyle q}$ . Thus ${\displaystyle g^{2}}$ divides ${\displaystyle r}$ , so writing ${\displaystyle e=c/1000}$ , ${\displaystyle f=d/k}$ and ${\displaystyle s=r/yard^{2}}$ , nosotros obtain the expression ${\displaystyle eastward^{two}+f^{2}=qs}$ for relatively prime ${\displaystyle e}$ and ${\displaystyle f}$ , and with ${\displaystyle due south<q/two}$ , since

${\displaystyle qs=e^{2}+f^{2}\leq c^{2}+d^{2}<\left({\frac {q}{ii}}\correct)^{2}+\left({\frac {q}{2}}\right)^{2}=q^{2}/2.}$

At present finally, the descent step: if ${\displaystyle q}$ is not the sum of 2 squares, and then by stride (3.) there must exist a cistron ${\displaystyle q_{i}}$ say of ${\displaystyle south}$ which is not the sum of two squares. Merely ${\displaystyle q_{i}\leq due south<q/2<q}$ and so repeating these steps (initially with ${\displaystyle e,f;q_{1}}$ in identify of ${\displaystyle a,b;q}$ , and so on ad infinitum) nosotros shall be able to observe a strictly decreasing infinite sequence ${\displaystyle q,q_{1},q_{2},\ldots }$ of positive integers which are not themselves the sums of two squares simply which carve up into a sum of 2 relatively prime squares. Since such an infinite descent is impossible, we conclude that ${\displaystyle q}$ must be expressible as a sum of two squares, as claimed.

v. Every prime of the course ${\displaystyle 4n+1}$ is a sum of two squares. (This is the master result of Euler's second paper).

If ${\displaystyle p=4n+1}$ , then by Fermat'south Little Theorem each of the numbers ${\displaystyle one,2^{4n},iii^{4n},\dots ,(4n)^{4n}}$ is congruent to one modulo ${\displaystyle p}$ . The differences ${\displaystyle 2^{4n}-i,3^{4n}-2^{4n},\dots ,(4n)^{4n}-(4n-1)^{4n}}$ are therefore all divisible by ${\displaystyle p}$ . Each of these differences can be factored as

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

Since ${\displaystyle p}$ is prime, information technology must carve up one of the two factors. If in any of the ${\displaystyle 4n-1}$ cases it divides the first factor, and so by the previous pace we conclude that ${\displaystyle p}$ is itself a sum of ii squares (since ${\displaystyle a}$ and ${\displaystyle b}$ differ past ${\displaystyle 1}$ , they are relatively prime). So information technology is enough to show that ${\displaystyle p}$ cannot e'er carve up the second gene. If information technology divides all ${\displaystyle 4n-1}$ differences ${\displaystyle 2^{2n}-1,3^{2n}-2^{2n},\dots ,(4n)^{2n}-(4n-ane)^{2n}}$ , then it would dissever all ${\displaystyle 4n-2}$ differences of successive terms, all ${\displaystyle 4n-3}$ differences of the differences, and and then forth. Since the ${\displaystyle k}$ th differences of the sequence ${\displaystyle 1^{1000},two^{k},iii^{one thousand},\dots }$ are all equal to ${\displaystyle chiliad!}$ (Finite deviation), the ${\displaystyle 2n}$ th differences would all be constant and equal to ${\displaystyle (2n)!}$ , which is certainly not divisible past ${\displaystyle p}$ . Therefore, ${\displaystyle p}$ cannot split up all the 2nd factors which proves that ${\displaystyle p}$ is indeed the sum of two squares.

Lagrange's proof through quadratic forms [edit]

Lagrange completed a proof in 1775^[fourteen] 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 ${\displaystyle ax^{2}+bxy+cy^{2}}$ with ${\displaystyle a,b,c}$ integers. A number ${\displaystyle n}$ is said to be represented by the course if there exist integers ${\displaystyle ten,y}$ such that ${\displaystyle due north=ax^{2}+bxy+cy^{2}}$ . Fermat's theorem on sums of two squares is then equivalent to the argument that a prime ${\displaystyle p}$ is represented past the form ${\displaystyle x^{two}+y^{2}}$ (i.east., ${\displaystyle a=c=1}$ , ${\displaystyle b=0}$ ) exactly when ${\displaystyle p}$ is congruent to ${\displaystyle one}$ modulo ${\displaystyle 4}$ .

The discriminant of the quadratic class is defined to be ${\displaystyle b^{2}-4ac}$ . The discriminant of ${\displaystyle x^{2}+y^{2}}$ is then equal to ${\displaystyle -iv}$ .

Two forms ${\displaystyle ax^{2}+bxy+cy^{two}}$ and ${\displaystyle a'x'^{2}+b'x'y'+c'y'^{two}}$ are equivalent if and only if there be substitutions with integer coefficients

${\displaystyle x=\alpha ten'+\beta y'}$

${\displaystyle y=\gamma x'+\delta y'}$

with ${\displaystyle \alpha \delta -\beta \gamma =\pm ane}$ such that, when substituted into the showtime course, yield the second. Equivalent forms are readily seen to take the same discriminant, and hence besides the same parity for the middle coefficient ${\displaystyle b}$ , which coincides with the parity of the discriminant. Moreover, it is clear that equivalent forms will stand for exactly the same integers, considering these kind of substitutions tin can be reversed by substitutions of the same kind.

Lagrange proved that all positive definite forms of discriminant −iv are equivalent. Thus, to evidence Fermat's theorem it is enough to find whatever positive definite class of discriminant −4 that represents ${\displaystyle p}$ . For example, one can use a form

${\displaystyle px^{2}+2mxy+\left({\frac {g^{2}+ane}{p}}\correct)y^{2},}$

where the commencement coefficient a = ${\displaystyle p}$ was called so that the form represents ${\displaystyle p}$ by setting x = 1, and y = 0, the coefficient b = 21000 is an arbitrary even number (as it must be, to go an even discriminant), and finally ${\displaystyle c={\frac {m^{two}+one}{p}}}$ is chosen so that the discriminant ${\displaystyle b^{two}-4ac=4m^{2}-4pc}$ is equal to −4, which guarantees that the form is indeed equivalent to ${\displaystyle ten^{ii}+y^{2}}$ . Of course, the coefficient ${\displaystyle c={\frac {1000^{two}+1}{p}}}$ must be an integer, so the trouble is reduced to finding some integer 1000 such that ${\displaystyle p}$ divides ${\displaystyle thou^{two}+ane}$ : or in other words, a 'square root of -1 modulo ${\displaystyle p}$ ' .

Nosotros claim such a foursquare root of ${\displaystyle -one}$ is given by ${\displaystyle K=\prod _{k=one}^{\frac {p-1}{2}}thou}$ . Firstly it follows from Euclid'south Fundamental Theorem of Arithmetic that ${\displaystyle ab\equiv 0{\pmod {p}}\iff a\equiv 0{\pmod {p}}\ \ {\hbox{or}}\ \ b\equiv 0{\pmod {p}}}$ . Consequently, ${\displaystyle a^{ii}\equiv ane{\pmod {p}}\iff a\equiv \pm 1{\pmod {p}}}$ : that is, ${\displaystyle \pm 1}$ are their own inverses modulo ${\displaystyle p}$ and this belongings is unique to them. It then follows from the validity of Euclidean division in the integers, and the fact that ${\displaystyle p}$ is prime number, that for every ${\displaystyle 2\leq a\leq p-2}$ the gcd of ${\displaystyle a}$ and ${\displaystyle p}$ may be expressed via the Euclidean algorithm yielding a unique and distinct changed ${\displaystyle a^{-1}\neq a}$ of ${\displaystyle a}$ modulo ${\displaystyle p}$ . In item therefore the product of all non-zero residues modulo ${\displaystyle p}$ is ${\displaystyle -1}$ . Let ${\displaystyle L=\prod _{50={\frac {p+one}{2}}}^{p-one}l}$ : from what has just been observed, ${\displaystyle KL\equiv -1{\pmod {p}}}$ . But by definition, since each term in ${\displaystyle Yard}$ may be paired with its negative in ${\displaystyle 50}$ , ${\displaystyle Fifty=(-i)^{\frac {p-i}{ii}}K}$ , which since ${\displaystyle p}$ is odd shows that ${\displaystyle K^{2}\equiv -1{\pmod {p}}\iff p\equiv ane{\pmod {4}}}$ , as required.

Dedekind's two proofs using Gaussian integers [edit]

Richard Dedekind gave at to the lowest degree 2 proofs of Fermat'southward theorem on sums of two squares, both using the arithmetical properties of the Gaussian integers, which are numbers of the class a +bi, where a and b are integers, and i is the square root of −1. One appears in department 27 of his exposition of ideals published in 1877; the 2nd appeared in Supplement Eleven to Peter Gustav Lejeune Dirichlet's Vorlesungen über Zahlentheorie, and was published in 1894.

1. Start proof. If ${\displaystyle p}$ is an odd prime, then we have ${\displaystyle i^{p-1}=(-1)^{\frac {p-1}{2}}}$ 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

${\displaystyle \omega ^{p}=(x+yi)^{p}\equiv ten^{p}+y^{p}i^{p}\equiv x+(-1)^{\frac {p-i}{two}}yi{\pmod {p}},}$

since the automorphism fixes the elements of Z/(p). In the current case, ${\displaystyle p=4n+1}$ for some integer northward, and so in the above expression for ω^p, the exponent (p-1)/ii of -ane is fifty-fifty. Hence the right hand side equals ω, then in this case the Frobenius endomorphism of Z[i]/(p) is the identity.

Kummer had already established that if f ∈ {1,two} is the order of the Frobenius automorphism of Z[i]/(p), and then the ideal ${\displaystyle (p)}$ in Z[i] would be a product of 2/f distinct prime ideals. (In fact, Kummer had established a much more general effect for any extension of Z obtained by adjoining a primitive m-th root of unity, where k was whatever positive integer; this is the instance k = 4 of that effect.) 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 ${\displaystyle N(x+iy)=x^{two}+y^{2}}$ , every platonic is primary and generated by a nonzero element of the ideal of minimal norm. Since the norm is multiplicative, the norm of a generator ${\displaystyle \alpha }$ of one of the platonic factors of (p) must be a strict divisor of ${\displaystyle N(p)=p^{2}}$ , and so that we must have ${\displaystyle p=N(\alpha )=Due north(a+bi)=a^{ii}+b^{two}}$ , which gives Fermat's theorem.

two. Second proof. This proof builds on Lagrange's result that if ${\displaystyle p=4n+1}$ is a prime number, and then there must exist an integer m such that ${\displaystyle g^{2}+1}$ is divisible by p (nosotros can also see this past Euler's criterion); it also uses the fact that the Gaussian integers are a unique factorization domain (considering they are a Euclidean domain). Since p ∈ Z does not divide either of the Gaussian integers ${\displaystyle 1000+i}$ and ${\displaystyle yard-i}$ (as it does not divide their imaginary parts), just it does separate their product ${\displaystyle m^{2}+1}$ , it follows that ${\displaystyle p}$ cannot be a prime number chemical 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 take only two factors (since the norm is multiplicative, and ${\displaystyle p^{two}=North(p)}$ , in that location tin can only exist upwardly to two factors of p), then it must exist of the form ${\displaystyle p=(10+yi)(x-yi)}$ for some integers ${\displaystyle x}$ and ${\displaystyle y}$ . This immediately yields that ${\displaystyle p=x^{2}+y^{two}}$ .

Proof by Minkowski'due south Theorem [edit]

For ${\displaystyle p}$ congruent to ${\displaystyle 1}$ modern ${\displaystyle 4}$ a prime, ${\displaystyle -1}$ is a quadratic balance mod ${\displaystyle p}$ by Euler's criterion. Therefore, there exists an integer ${\displaystyle 1000}$ such that ${\displaystyle p}$ divides ${\displaystyle m^{2}+ane}$ . Let ${\displaystyle {\hat {i}},{\hat {j}}}$ be the standard basis elements for the vector infinite ${\displaystyle \mathbb {R} ^{2}}$ and prepare ${\displaystyle {\vec {u}}={\hat {i}}+m{\chapeau {j}}}$ and ${\displaystyle {\vec {5}}=0{\lid {i}}+p{\hat {j}}}$ . Consider the lattice ${\displaystyle S=\{a{\vec {u}}+b{\vec {five}}\mid a,b\in \mathbb {Z} \}}$ . If ${\displaystyle {\vec {due west}}=a{\vec {u}}+b{\vec {v}}=a{\hat {i}}+(am+bp){\hat {j}}\in Southward}$ then ${\displaystyle \|{\vec {w}}\|^{2}\equiv a^{two}+(am+bp)^{ii}\equiv a^{2}(1+m^{2})\equiv 0{\pmod {p}}}$ . Thus ${\displaystyle p}$ divides ${\displaystyle \|{\vec {west}}\|^{2}}$ for whatsoever ${\displaystyle {\vec {westward}}\in S}$ .

The area of the central parallelogram of the lattice is ${\displaystyle p}$ . The expanse of the open disk, ${\displaystyle D}$ , of radius ${\displaystyle {\sqrt {2p}}}$ centered around the origin is ${\displaystyle ii\pi p>4p}$ . Furthermore, ${\displaystyle D}$ is convex and symmetrical almost the origin. Therefore, by Minkowski's theorem there exists a nonzero vector ${\displaystyle {\vec {due west}}\in S}$ such that ${\displaystyle {\vec {w}}\in D}$ . Both ${\displaystyle \|{\vec {w}}\|^{two}<2p}$ and ${\displaystyle p\mid \|{\vec {westward}}\|^{2}}$ so ${\displaystyle p=\|{\vec {w}}\|^{2}}$ . Hence ${\displaystyle p}$ is the sum of the squares of the components of ${\displaystyle {\vec {west}}}$ .

Zagier's "one-judgement proof" [edit]

Let ${\displaystyle p=4k+1}$ exist prime, let ${\displaystyle \mathbb {N} }$ announce the natural numbers (with or without zero), and consider the finite ready ${\displaystyle S=\{(x,y,z)\in \mathbb {North} ^{3}:x^{two}+4yz=p\}}$ of triples of numbers. Then ${\displaystyle Due south}$ has two involutions: an obvious i ${\displaystyle (10,y,z)\mapsto (10,z,y)}$ whose fixed points ${\displaystyle (10,y,y)}$ stand for to representations of ${\displaystyle p}$ as a sum of two squares, and a more complicated one,

${\displaystyle (ten,y,z)\mapsto {\begin{cases}(x+2z,~z,~y-x-z),\quad {\textrm {if}}\,\,\,x<y-z\\(2y-x,~y,~ten-y+z),\quad {\textrm {if}}\,\,\,y-z<x<2y\\(x-2y,~x-y+z,~y),\quad {\textrm {if}}\,\,\,10>2y\end{cases}}}$

which has exactly one fixed signal ${\displaystyle (1,1,1000)}$ . Ii involutions over the aforementioned finite gear up must have sets of fixed points with the same parity, and since the second involution has an odd number of fixed points, then does the first. Nada is even, then the first involution has a nonzero number of fixed points, any 1 of which gives a representation of ${\displaystyle p}$ equally a sum of ii squares.

This proof, due to Zagier, is a simplification of an before proof by Heath-Brown, which in turn was inspired by a proof of Liouville. The technique of the proof is a combinatorial counterpart of the topological principle that the Euler characteristics of a topological infinite with an involution and of its stock-still-point ready take 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 postal service and this Mathologer YouTube video Why was this visual proof missed for 400 years? (Fermat'southward two square theorem) on YouTube.

Proof with segmentation theory [edit]

In 2016, A. David Christopher gave a partition-theoretic proof past because partitions of the odd prime ${\displaystyle north}$ having exactly two sizes ${\displaystyle a_{i}(i=i,ii)}$ , each occurring exactly ${\displaystyle a_{i}}$ times, and by showing that at least ane such partition exists if ${\displaystyle n}$ is coinciding to 1 modulo four.^[15]

Run across as well [edit]

• Legendre'due south 3-square theorem
• Lagrange's four-square theorem
• Landau–Ramanujan constant
• Thue's lemma

References [edit]

• D. A. Cox (1989). Primes of the Course x² + ny² . Wiley-Interscience. ISBN0-471-50654-0. *Richard Dedekind, The theory of algebraic integers.
• L. E. Dickson. History of the Theory of Numbers Vol. two. Chelsea Publishing Co., New York 1920
• Harold Thou. Edwards, Fermat's Terminal Theorem. A genetic introduction to algebraic number theory. Graduate Texts in Mathematics no. fifty, Springer-Verlag, NY, 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, ISBNane-56881-006-7
• D. R. Heath-Chocolate-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 Academy Printing, 1996. ISBN 0-521-56518-9
• Don Zagier, A one-sentence proof that every prime number p ≡ 1 mod four is a sum of two squares. Amer. Math. Monthly 97 (1990), no. ii, 144, doi:10.2307/2323918

Notes [edit]

1. ^ For a proof of the converse see for case 20.1, Theorems 367 and 368, in: Grand.H. Hardy and E.Chiliad. Wright. An introduction to the theory of numbers, Oxford 1938.
2. ^ Simon Stevin. l'Arithmétique de Simon Stevin de Bruges, annotated past Albert Girard, Leyde 1625, p. 622.
3. ^ L. Eastward. Dickson, History of the Theory of Numbers, Vol. II, Ch. VI, p. 227. "A. Girard ... had already made a decision of the numbers expressible as a sum of two integral squares: every square, every prime number 4n+ane, a product formed of such numbers, and the double of the foregoing"
4. ^ 50. E. Dickson, History of the Theory of Numbers, Vol. II, Ch. Six, p. 228.
5. ^ Wagon, Stan (1990), "Editor's Corner: The Euclidean Algorithm Strikes Again", American Mathematical Monthly, 97 (2): 125, doi:10.2307/2323912, MR 1041889 .
6. ^ De numerus qui sunt aggregata quorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/3), 1758, 3-40)
7. ^ Demonstratio theorematis FERMATIANI omnem numerum primum formae 4n+1 esse summam duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae five (1754/5), 1760, 3-xiii)
8. ^ Zagier, D. (1990), "A one-sentence proof that every prime number p ≡ 1 (mod 4) is a sum of ii squares", American Mathematical Monthly, 97 (2): 144, doi:10.2307/2323918, MR 1041893 .
9. ^ A. David Christopher. "A partitioning-theoretic proof of Fermat'due south Two Squares Theorem", Discrete Mathematics 339:iv:1410–1411 (6 April 2016) doi:10.1016/j.disc.2015.12.002
10. ^ Euler à Goldbach, lettre CXXV
11. ^ De numerus qui sunt aggregata duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/three), 1758, three-twoscore) [ane]
12. ^ Demonstratio theorematis FERMATIANI omnem numerum primum formae 4n+1 esse summam duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 5 (1754/5), 1760, iii-13) [two]
13. ^ The summary is based on Edwards book, pages 45-48.
14. ^ Nouv. Mém. Acad. Berlin, année 1771, 125; ibid. année 1773, 275; ibid année 1775, 351.
15. ^ A. David Christopher, A partition-theoretic proof of Fermat's 2 Squares Theorem", Discrete Mathematics, 339 (2016) 1410–1411.

External links [edit]

• Two more proofs at PlanetMath.org
• "A ane-judgement proof of the theorem". Archived from the original on five February 2012. {{cite web}}: CS1 maint: unfit URL (link)
• Fermat's two squares theorem, D. R. Heath-Brown, 1984.

kittsforre1965.blogspot.com

Source: https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares

Share this post