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 after Pierre de Fermat, run into Fermat's theorem.

In condiment number theory, Fermat's theorem on sums of 2 squares states that an odd prime number p tin be expressed as:

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

with 10 and y integers, if and only if

${\displaystyle p\equiv i{\pmod {4}}.}$

The prime number numbers for which this is true are called Pythagorean primes. For instance, the primes five, 13, 17, 29, 37 and 41 are all congruent to ane modulo iv, and they tin can be expressed as sums of two squares in the following ways:

${\displaystyle 5=ane^{2}+ii^{2},\quad 13=2^{2}+iii^{2},\quad 17=i^{2}+four^{ii},\quad 29=ii^{2}+5^{2},\quad 37=1^{2}+6^{two},\quad 41=4^{2}+5^{two}.}$

On the other manus, the primes iii, 7, 11, 19, 23 and 31 are all congruent to 3 modulo 4, and none of them tin can be expressed as the sum of two squares. This is the easier role of the theorem, and follows immediately from the ascertainment 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 tin can be written every bit the sum of two squares is itself expressible as the sum of two squares, past applying Fermat'due south theorem to the prime factorization of any positive integer n, we see that if all the prime factors of n coinciding to 3 modulo iv occur to an even exponent, then northward is expressible every bit a sum of ii squares. The antipodal also holds.^[1] This generalization of Fermat's theorem is known as the sum of two squares theorem.

History [edit]

Albert Girard was the commencement 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 argument that every prime number p of the grade 4n+one is the sum of 2 squares is sometimes called Girard's theorem.^[iv] For his part, Fermat wrote an elaborate version of the statement (in which he besides gave the number of possible expressions of the powers of p as a sum of two squares) in a letter of the alphabet to Marin Mersenne dated December 25, 1640: for this reason this version of the theorem is sometimes called Fermat'southward Christmas theorem.

Gaussian primes [edit]

Fermat's theorem on sums of 2 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 N(a+ib)=a^{2}+b^{two}}$ of a Gaussian integer is an integer equal to the foursquare 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 form a main platonic domain. This implies that Gaussian primes tin 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 i, −ane, 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 first case occurs when ${\displaystyle p=4k+iii,}$ and that the 2nd case occurs when ${\displaystyle p=4k+1}$ and ${\displaystyle p=2.}$ The final case is not considered in Fermat'south statement, but is lilliputian, as ${\displaystyle 2=i^{2}+i^{ii}=Northward(one+i).}$

[edit]

Above betoken of view on Fermat'south theorem is a special example 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, then an odd prime number p, not dividing d, is either a prime number 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 constabulary 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 platonic norm if and merely

${\displaystyle 4p=a^{two}-db^{2},}$

with a and b both integers.

In a letter to Blaise Pascal dated September 25, 1654 Fermat appear the post-obit two results that are essentially the special cases ${\displaystyle d=-2}$ and ${\displaystyle d=-3.}$ If p is an odd prime, so

${\displaystyle p=x^{ii}+2y^{ii}\iff p\equiv ane{\mbox{ or }}p\equiv 3{\pmod {8}},}$

${\displaystyle p=ten^{ii}+3y^{ii}\iff p\equiv one{\pmod {3}}.}$

Fermat wrote also:

If two primes which terminate in 3 or seven and surpass by 3 a multiple of iv are multiplied, then their product volition exist composed of a square and the quintuple of another square.

In other words, if p, q are of the form xxk + three or xxk + 7, then pq = x ² + 5y ² . Euler later extended this to the conjecture that

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

${\displaystyle 2p=x^{two}+5y^{2}\iff p\equiv 3{\mbox{ or }}p\equiv 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 ${\displaystyle {\mathcal {O}}_{\sqrt {-5}}}$ is not a main ideal domain, contrarily to ${\displaystyle {\mathcal {O}}_{\sqrt {-2}}}$ and ${\displaystyle {\mathcal {O}}_{\sqrt {-3}}.}$

Algorithm [edit]

There is a niggling algorithm for decomposing a prime of the grade ${\displaystyle p=4k+1}$ into a sum of two squares: For all north such ${\displaystyle 1\leq due north<{\sqrt {p}}}$ , exam whether the square root of ${\displaystyle p-n^{2}}$ is an integer. If this the example, one has got the decomposition.

However the input size of the algorithm is ${\displaystyle \log p,}$ the number of digits of p (upwardly 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}{two}}\correct),}$ and thus exponential in the input size. So the computational complexity of this algorithm is exponential.

An algorithm with a polynomial complication has been described by Stan Wagon in 1990, based on work by Serret and Hermite (1848), and Cornacchia (1908).^[5]

Description [edit]

Given an odd prime number ${\displaystyle p}$ in the form ${\displaystyle 4k+1}$ , offset notice ${\displaystyle x}$ such that ${\displaystyle ten^{2}\equiv -1{\pmod {p}}}$ . This tin can be done by finding a Quadratic non-residue modulo ${\displaystyle p}$ , say ${\displaystyle q}$ , and letting ${\displaystyle ten=q^{\frac {p-1}{4}}{\pmod {p}}}$ .

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

Once ${\displaystyle x}$ is adamant, i can utilise the Euclidean algorithm with ${\displaystyle p}$ and ${\displaystyle ten}$ . Announce the first two remainders that are less than the square root of ${\displaystyle p}$ as ${\displaystyle a}$ and ${\displaystyle b}$ . Then it will exist the case that ${\displaystyle a^{ii}+b^{2}=p}$ .

Instance [edit]

Have ${\displaystyle p=97}$ . A possible quadratic non-rest for 97 is thirteen, 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(iv)+9,}$$

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

$${\displaystyle 9=iv(two)+ane,}$$

$${\displaystyle iv=1(iv).}$$

The outset two remainders smaller than the foursquare root of 97 are 9 and 4; and indeed we take ${\displaystyle 97=9^{ii}+4^{ii}}$ , as expected.

Proofs [edit]

Fermat usually did non write down proofs of his claims, and he did not provide a proof of this statement. The get-go proof was found by Euler later on much try 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).^{[half dozen] [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 (fine art. 182). Dedekind gave at to the lowest degree two proofs based on the arithmetic of the Gaussian integers. In that location is an elegant proof using Minkowski's theorem most convex sets. Simplifying an before short proof due to Heath-Brown (who was inspired by Liouville's idea), Zagier presented a non-constructive one-sentence proof in 1990.^[viii] And more than recently Christopher gave a sectionalisation-theoretic proof.^[9]

Euler'due south proof past infinite descent [edit]

Euler succeeded in proving Fermat's theorem on sums of ii squares in 1749, when he was twoscore-two years old. He communicated this in a alphabetic character to Goldbach dated 12 April 1749.^[ten] The proof relies on space descent, and is only briefly sketched in the alphabetic character. The full proof consists in five steps and is published in two papers. The first four steps are Propositions 1 to 4 of the offset paper^[11] and practice non correspond exactly to the four steps below. The 5th stride beneath is from the second paper.^{[12] [13]}

For the avoidance of ambiguity, zero volition always be a valid possible constituent of "sums of 2 squares", so for instance every square of an integer is trivially expressible equally the sum of ii squares by setting one of them to be null.

i. 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^{two}+q^{ii})=(ap+bq)^{two}+(aq-bp)^{ii}}$

due to Diophantus.

2. If a number which is a sum of two squares is divisible by a prime number which is a sum of two squares, and so the quotient is a sum of ii squares. (This is Euler's offset Proffer).

Indeed, suppose for case that ${\displaystyle a^{two}+b^{2}}$ is divisible by ${\displaystyle p^{two}+q^{ii}}$ and that this latter is a prime. And so ${\displaystyle p^{2}+q^{two}}$ divides

${\displaystyle (lead-aq)(pb+aq)=p^{ii}b^{2}-a^{2}q^{2}=p^{2}(a^{ii}+b^{2})-a^{2}(p^{ii}+q^{2}).}$

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

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

(Diophantus's identity) it follows that ${\displaystyle p^{2}+q^{two}}$ must separate ${\displaystyle (ap+bq)^{two}}$ . And so the equation tin can exist 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)^{ii}+\left({\frac {aq-bp}{p^{2}+q^{two}}}\right)^{2}}$

and thus expresses the quotient as a sum of two squares, as claimed.

On the other manus if ${\displaystyle p^{ii}+q^{2}}$ divides ${\displaystyle pb+aq}$ , a like argument holds by using the following variant of Diophantus's identity:

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

iii. If a number which can be written as a sum of two squares is divisible by a number which is non a sum of ii squares, and so the caliber has a factor which is not a sum of ii squares. (This is Euler's second Proffer).

Suppose ${\displaystyle q}$ is a number not expressible as a sum of two squares, which divides ${\displaystyle a^{2}+b^{two}}$ . Write the quotient, factored into its (peradventure repeated) prime number factors, as ${\displaystyle p_{1}p_{2}\cdots p_{north}}$ so that ${\displaystyle a^{2}+b^{ii}=qp_{one}p_{2}\cdots p_{n}}$ . If all factors ${\displaystyle p_{i}}$ can be written as sums of two squares, and so we can divide ${\displaystyle a^{ii}+b^{2}}$ successively by ${\displaystyle p_{1}}$ , ${\displaystyle p_{ii}}$ , etc., and applying footstep (2.) in a higher place we deduce that each successive, smaller, caliber is a sum of two squares. If we get all the way down to ${\displaystyle q}$ so ${\displaystyle q}$ itself would accept to be equal to the sum of two squares, which is a contradiction. So at to the lowest degree 1 of the primes ${\displaystyle p_{i}}$ is non the sum of two squares.

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

Permit ${\displaystyle a,b}$ be relatively prime positive integers: without loss of generality ${\displaystyle a^{ii}+b^{2}}$ is not itself prime, otherwise there is zippo to evidence. Let ${\displaystyle q}$ therefore exist a proper gene of ${\displaystyle a^{2}+b^{2}}$ , not necessarily prime: we wish to evidence that ${\displaystyle q}$ is a sum of two squares. Again, we lose nothing by bold ${\displaystyle q>2}$ since the case ${\displaystyle q=2=one^{2}+1^{2}}$ is obvious.

Let ${\displaystyle m,n}$ 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 absolute value strictly less than ${\displaystyle q/two}$ : indeed, when ${\displaystyle q>two}$ is even, gcd ${\displaystyle (a,q/two)=1}$ ; otherwise since gcd ${\displaystyle (a,q/2)\mid q/2\mid q\mid a^{2}+b^{two}}$ , nosotros 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^{2}+n^{two}q^{2}+2nqd+d^{2}=Aq+(c^{2}+d^{2})}$

uniquely defining a non-negative integer ${\displaystyle A}$ . Since ${\displaystyle q}$ divides both ends of this equation sequence it follows that ${\displaystyle c^{ii}+d^{2}}$ must also be divisible past ${\displaystyle q}$ : say ${\displaystyle c^{2}+d^{2}=qr}$ . Let ${\displaystyle g}$ 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 1000^{2}}$ divides ${\displaystyle r}$ , so writing ${\displaystyle due east=c/m}$ , ${\displaystyle f=d/g}$ and ${\displaystyle s=r/g^{two}}$ , we obtain the expression ${\displaystyle e^{2}+f^{ii}=qs}$ for relatively prime number ${\displaystyle e}$ and ${\displaystyle f}$ , and with ${\displaystyle s<q/2}$ , since

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

Now finally, the descent step: if ${\displaystyle q}$ is non the sum of two squares, then by step (three.) in that location must be a factor ${\displaystyle q_{1}}$ say of ${\displaystyle due south}$ which is non the sum of two squares. But ${\displaystyle q_{1}\leq s<q/2<q}$ and so repeating these steps (initially with ${\displaystyle eastward,f;q_{ane}}$ in place of ${\displaystyle a,b;q}$ , and so on advert infinitum) we shall be able to detect a strictly decreasing infinite sequence ${\displaystyle q,q_{i},q_{two},\ldots }$ of positive integers which are non themselves the sums of two squares but which divide into a sum of two relatively prime squares. Since such an infinite descent is impossible, nosotros conclude that ${\displaystyle q}$ must exist expressible as a sum of two squares, as claimed.

5. Every prime number of the course ${\displaystyle 4n+i}$ is a sum of two squares. (This is the main result of Euler'south second paper).

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

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

Since ${\displaystyle p}$ is prime, it must divide i of the 2 factors. If in any of the ${\displaystyle 4n-1}$ cases it divides the first cistron, then by the previous step we conclude that ${\displaystyle p}$ is itself a sum of 2 squares (since ${\displaystyle a}$ and ${\displaystyle b}$ differ by ${\displaystyle 1}$ , they are relatively prime). So information technology is enough to show that ${\displaystyle p}$ cannot always divide the second cistron. If it divides all ${\displaystyle 4n-1}$ differences ${\displaystyle 2^{2n}-1,iii^{2n}-2^{2n},\dots ,(4n)^{2n}-(4n-1)^{2n}}$ , then it would divide all ${\displaystyle 4n-2}$ differences of successive terms, all ${\displaystyle 4n-3}$ differences of the differences, and and so forth. Since the ${\displaystyle k}$ th differences of the sequence ${\displaystyle 1^{m},ii^{k},3^{m},\dots }$ are all equal to ${\displaystyle k!}$ (Finite departure), the ${\displaystyle 2n}$ thursday differences would all exist abiding and equal to ${\displaystyle (2n)!}$ , which is certainly not divisible by ${\displaystyle p}$ . Therefore, ${\displaystyle p}$ cannot dissever all the second factors which proves that ${\displaystyle p}$ is indeed the sum of two squares.

Lagrange'south proof through quadratic forms [edit]

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

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

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

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

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

with ${\displaystyle \alpha \delta -\beta \gamma =\pm ane}$ such that, when substituted into the first course, yield the second. Equivalent forms are readily seen to accept the same discriminant, and hence also the same parity for the middle coefficient ${\displaystyle b}$ , which coincides with the parity of the discriminant. Moreover, information technology is clear that equivalent forms will represent exactly the aforementioned integers, because these kind of substitutions tin be reversed past substitutions of the aforementioned kind.

Lagrange proved that all positive definite forms of discriminant −4 are equivalent. Thus, to prove Fermat'south theorem information technology is plenty to find any positive definite form of discriminant −4 that represents ${\displaystyle p}$ . For example, 1 can utilise a form

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

where the kickoff coefficient a = ${\displaystyle p}$ was called so that the form represents ${\displaystyle p}$ by setting x = 1, and y = 0, the coefficient b = iim is an arbitrary even number (as information technology must be, to get an even discriminant), and finally ${\displaystyle c={\frac {thousand^{2}+1}{p}}}$ is called 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 {m^{2}+one}{p}}}$ must be an integer, then the problem is reduced to finding some integer one thousand such that ${\displaystyle p}$ divides ${\displaystyle thousand^{2}+1}$ : or in other words, a 'square root of -one modulo ${\displaystyle p}$ ' .

We claim such a square root of ${\displaystyle -i}$ is given by ${\displaystyle Yard=\prod _{k=i}^{\frac {p-ane}{two}}k}$ . Firstly it follows from Euclid'southward 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 i{\pmod {p}}\iff a\equiv \pm 1{\pmod {p}}}$ : that is, ${\displaystyle \pm 1}$ are their ain inverses modulo ${\displaystyle p}$ and this property is unique to them. It then follows from the validity of Euclidean segmentation in the integers, and the fact that ${\displaystyle p}$ is prime, 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 inverse ${\displaystyle a^{-1}\neq a}$ of ${\displaystyle a}$ modulo ${\displaystyle p}$ . In particular therefore the product of all non-zilch residues modulo ${\displaystyle p}$ is ${\displaystyle -1}$ . Let ${\displaystyle L=\prod _{l={\frac {p+1}{2}}}^{p-one}50}$ : from what has merely been observed, ${\displaystyle KL\equiv -1{\pmod {p}}}$ . Simply by definition, since each term in ${\displaystyle K}$ may be paired with its negative in ${\displaystyle 50}$ , ${\displaystyle L=(-one)^{\frac {p-1}{ii}}K}$ , which since ${\displaystyle p}$ is odd shows that ${\displaystyle G^{ii}\equiv -1{\pmod {p}}\iff p\equiv 1{\pmod {four}}}$ , every bit required.

Dedekind'southward 2 proofs using Gaussian integers [edit]

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 11 to Peter Gustav Lejeune Dirichlet's Vorlesungen über Zahlentheorie, and was published in 1894.

ane. Outset proof. If ${\displaystyle p}$ is an odd prime, so we have ${\displaystyle i^{p-1}=(-i)^{\frac {p-1}{ii}}}$ in the Gaussian integers. Consequently, writing a Gaussian integer ω =x +iy with 10,y ∈Z and applying the Frobenius automorphism in Z[i]/(p), one finds

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

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

Kummer had already established that if f ∈ {1,ii} is the order of the Frobenius automorphism of Z[i]/(p), then the ideal ${\displaystyle (p)}$ in Z[i] would be a product of two/f distinct prime ethics. (In fact, Kummer had established a much more full general result for any extension of Z obtained by adjoining a primitive m-thursday root of unity, where m was any positive integer; this is the instance m = 4 of that result.) Therefore, the ideal (p) is the product of two dissimilar prime ethics in Z[i]. Since the Gaussian integers are a Euclidean domain for the norm function ${\displaystyle N(x+iy)=x^{two}+y^{two}}$ , 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 ${\displaystyle \alpha }$ of 1 of the ideal factors of (p) must be a strict divisor of ${\displaystyle Due north(p)=p^{two}}$ , so that we must have ${\displaystyle p=North(\alpha )=Due north(a+bi)=a^{2}+b^{2}}$ , which gives Fermat's theorem.

ii. 2d proof. This proof builds on Lagrange'southward result that if ${\displaystyle p=4n+ane}$ is a prime number, and then there must exist an integer thou such that ${\displaystyle m^{2}+1}$ is divisible by p (nosotros tin also run across this by Euler's criterion); information technology 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 ${\displaystyle m+i}$ and ${\displaystyle m-i}$ (equally it does non divide their imaginary parts), merely it does divide their production ${\displaystyle chiliad^{two}+1}$ , it follows that ${\displaystyle p}$ cannot be a prime element in the Gaussian integers. Nosotros must therefore take a nontrivial factorization of p in the Gaussian integers, which in view of the norm can have merely two factors (since the norm is multiplicative, and ${\displaystyle p^{ii}=Northward(p)}$ , in that location can only be up to two factors of p), and so it must exist of the form ${\displaystyle p=(x+yi)(x-yi)}$ for some integers ${\displaystyle x}$ and ${\displaystyle y}$ . This immediately yields that ${\displaystyle p=x^{2}+y^{2}}$ .

Proof by Minkowski'southward Theorem [edit]

For ${\displaystyle p}$ congruent to ${\displaystyle 1}$ modernistic ${\displaystyle iv}$ a prime, ${\displaystyle -one}$ is a quadratic residue modernistic ${\displaystyle p}$ past Euler's criterion. Therefore, in that location exists an integer ${\displaystyle m}$ such that ${\displaystyle p}$ divides ${\displaystyle thousand^{ii}+1}$ . Let ${\displaystyle {\hat {i}},{\chapeau {j}}}$ be the standard basis elements for the vector space ${\displaystyle \mathbb {R} ^{two}}$ and set ${\displaystyle {\vec {u}}={\hat {i}}+m{\lid {j}}}$ and ${\displaystyle {\vec {v}}=0{\hat {i}}+p{\chapeau {j}}}$ . Consider the lattice ${\displaystyle Due south=\{a{\vec {u}}+b{\vec {v}}\mid a,b\in \mathbb {Z} \}}$ . If ${\displaystyle {\vec {westward}}=a{\vec {u}}+b{\vec {v}}=a{\hat {i}}+(am+bp){\hat {j}}\in Southward}$ then ${\displaystyle \|{\vec {due west}}\|^{two}\equiv a^{2}+(am+bp)^{ii}\equiv a^{2}(1+k^{ii})\equiv 0{\pmod {p}}}$ . Thus ${\displaystyle p}$ divides ${\displaystyle \|{\vec {w}}\|^{two}}$ for whatsoever ${\displaystyle {\vec {w}}\in S}$ .

The surface area of the fundamental 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 two\pi p>4p}$ . Furthermore, ${\displaystyle D}$ is convex and symmetrical about the origin. Therefore, by Minkowski'due south theorem in that location exists a nonzero vector ${\displaystyle {\vec {west}}\in S}$ such that ${\displaystyle {\vec {w}}\in D}$ . Both ${\displaystyle \|{\vec {w}}\|^{2}<2p}$ and ${\displaystyle p\mid \|{\vec {w}}\|^{2}}$ and then ${\displaystyle p=\|{\vec {due west}}\|^{2}}$ . Hence ${\displaystyle p}$ is the sum of the squares of the components of ${\displaystyle {\vec {w}}}$ .

Zagier'due south "i-sentence proof" [edit]

Let ${\displaystyle p=4k+1}$ exist prime, let ${\displaystyle \mathbb {Due north} }$ denote the natural numbers (with or without zero), and consider the finite set ${\displaystyle S=\{(10,y,z)\in \mathbb {N} ^{3}:ten^{2}+4yz=p\}}$ of triples of numbers. Then ${\displaystyle South}$ has two involutions: an obvious ane ${\displaystyle (x,y,z)\mapsto (x,z,y)}$ whose stock-still points ${\displaystyle (x,y,y)}$ correspond to representations of ${\displaystyle p}$ as a sum of 2 squares, and a more than complicated one,

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

which has exactly one fixed point ${\displaystyle (1,i,yard)}$ . Ii involutions over the same finite set up must accept sets of stock-still points with the same parity, and since the 2nd involution has an odd number of fixed points, then does the get-go. Zero is even, so the first involution has a nonzero number of fixed points, any one of which gives a representation of ${\displaystyle p}$ equally a sum of 2 squares.

This proof, due to Zagier, is a simplification of an earlier proof by Heath-Brownish, 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 stock-still-point set accept 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 mail service and this Mathologer YouTube video Why was this visual proof missed for 400 years? (Fermat'due south two foursquare theorem) on YouTube.

Proof with division theory [edit]

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

Run across as well [edit]

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

References [edit]

• D. A. Cox (1989). Primes of the Form 10² + ny² . Wiley-Interscience. ISBN0-471-50654-0. *Richard Dedekind, The theory of algebraic integers.
• L. East. Dickson. History of the Theory of Numbers Vol. 2. Chelsea Publishing Co., New York 1920
• Harold M. Edwards, Fermat'south 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. past Arthur A. Clarke. Springer-Verlag, 1986.
• Goldman, Jay R. (1998), The Queen of Mathematics: A historically motivated guide to Number Theory , A K Peters, ISBN1-56881-006-vii
• 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 1-sentence proof that every prime p ≡ 1 mod 4 is a sum of two squares. Amer. Math. Monthly 97 (1990), no. 2, 144, doi:10.2307/2323918

Notes [edit]

1. ^ For a proof of the converse come across for instance 20.one, Theorems 367 and 368, in: G.H. Hardy and E.M. 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. ^ 50. Eastward. Dickson, History of the Theory of Numbers, Vol. Ii, Ch. VI, p. 227. "A. Girard ... had already made a conclusion of the numbers expressible as a sum of two integral squares: every square, every prime 4n+i, a production formed of such numbers, and the double of the foregoing"
4. ^ L. E. Dickson, History of the Theory of Numbers, Vol. II, Ch. Vi, p. 228.
5. ^ Wagon, Stan (1990), "Editor'southward 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 v (1754/5), 1760, 3-thirteen)
8. ^ Zagier, D. (1990), "A one-sentence proof that every prime number p ≡ 1 (modern 4) is a sum of two squares", American Mathematical Monthly, 97 (2): 144, doi:10.2307/2323918, MR 1041893 .
9. ^ A. David Christopher. "A partitioning-theoretic proof of Fermat's Two Squares Theorem", Detached Mathematics 339:4:1410–1411 (6 Apr 2016) doi:ten.1016/j.disc.2015.12.002
10. ^ Euler à Goldbach, lettre CXXV
11. ^ De numerus qui sunt aggregata duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae iv (1752/3), 1758, iii-xl) [i]
12. ^ Demonstratio theorematis FERMATIANI omnem numerum primum formae 4n+ane esse summam duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae v (1754/5), 1760, three-thirteen) [ii]
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 sectionalization-theoretic proof of Fermat's Two Squares Theorem", Discrete Mathematics, 339 (2016) 1410–1411.

External links [edit]

• Ii more proofs at PlanetMath.org
• "A one-sentence proof of the theorem". Archived from the original on 5 February 2012. {{cite web}}: CS1 maint: unfit URL (link)
• Fermat's 2 squares theorem, D. R. Heath-Chocolate-brown, 1984.

wilkeswilty1969.blogspot.com

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

Share this post