Fermat's Theorem On Sums Of Two Squares

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime ''p'' can be expressed as:

:$p = x^2 + y^2,$

with ''x'' and ''y'' integers, if and only if

:$p \equiv 1 \pmod.$

The prime numbers for which this is true are called Pythagorean primes.
For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and they can be expressed as sums of two squares in the following ways:

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

On the other hand, the primes 3, 7, 11, 19, 23 and 31 are all congruent to 3 modulo 4, and none of them can be expressed as the sum of two squares. This is the easier part of the theorem, and follows immediately from the observation that all squares are congruent to 0 or 1 modulo 4.

Since the Diophantus identity implies that the product of two integers each of which can be written as the sum of two squares is itself expressible as the sum of two squares, by applying Fermat's theorem to the prime factorization of any positive integer ''n'', we see that if all the prime factors of ''n'' congruent to 3 modulo 4 occur to an even exponent, then ''n'' is expressible as a sum of two squares. The converse also holds. This generalization of Fermat's theorem is known as the sum of two squares theorem.

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. The statement that every prime ''p'' of the form ''4n+1'' is the sum of two squares is sometimes called ''Girard's theorem''. 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 $a+ib$ such that and are integers. The ''norm'' $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 and ).

The multiplicative property of the norm implies that a prime number is either a Gaussian prime or the norm of a Gaussian prime. Fermat's theorem asserts that the first case occurs when $p=4k+3,$ and that the second case occurs when $p=4k+1$ and $p=2.$ The last case is not considered in Fermat's statement, but is trivial, as $2 = 1^2+1^2 =N(1+i).$

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. In summary, if $\mathcal O_\sqrt$ is the ring of algebraic integers in the quadratic field, then an odd prime number , not dividing , is either a prime element in $\mathcal O_\sqrt,$ or the ideal norm of an ideal of $\mathcal O_\sqrt,$ which is necessarily prime. Moreover, the law of quadratic reciprocity allows distinguishing the two cases in terms of congruences. If $\mathcal O_\sqrt$ is a principal ideal domain, then is an ideal norm if and only
:$4p=a^2-db^2,$
with and both integers.

In a letter to Blaise Pascal dated September 25, 1654 Fermat announced the following two results that are essentially the special cases $d=-2$ and $d=-3.$ If is an odd prime, then
:$p = x^2 + 2y^2 \iff p\equiv 1\mboxp\equiv 3\pmod,$
:$p= x^2 + 3y^2 \iff p\equiv 1 \pmod.$

Fermat wrote also:
: ''If two primes which end in 3 or 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.''
In other words, if are of the form or , then . Euler later extended this to the conjecture that
:$p = x^2 + 5y^2 \iff p\equiv 1\mboxp\equiv 9\pmod,$
:$2p = x^2 + 5y^2 \iff p\equiv 3\mboxp\equiv 7\pmod.$

Both Fermat's assertion and Euler's conjecture were established by Joseph-Louis Lagrange for decomposing a prime of the form $p=4k+1$ into a sum of two squares: For all such $1\le n<\sqrt p$, test whether the square root of $p-n^2$ is an integer. If this the case, one has got the decomposition.

However the input size of the algorithm is $\log p,$ the number of digits of (up to a constant factor that depends on the numeral base). The number of needed tests is of the order of $\sqrt p = \exp \left (\frac 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).

Description

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

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

Once $x$ is determined, one can apply the Euclidean algorithm with $p$ and $x$. Denote the first two remainders that are less than the square root of $p$ as $a$ and $b$. Then it will be the case that $a^2+b^2=p$.

Example

Take $p = 97$. A possible quadratic non-residue for 97 is 13, since $13^\frac\equiv-1 \pmod$. so we let $x=13^\frac=22 \pmod$.
The Euclidean algorithm applied to 97 and 22 yields:
$97 = 22(4) + 9,$
$22 = 9(2) + 4,$
$9 = 4(2) + 1,$
$4 = 1(4).$
The first two remainders smaller than the square root of 97 are 9 and 4; and indeed we have $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). Lagrange

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases