Fermat's theorem on sums of two squares

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Fermat%27s_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:

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

with x and y integers, if and only if

${\displaystyle p\equiv 1(\mathrm{mod}4).}$

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:

${\displaystyle 5=1^2+2^2,13=2^2+3^2,17=1^2+4^2,29=2^2+5^2,37=1^2+6^2,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, characterizing the positive integers (not necessarily primes) that are 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 ${\displaystyle a+ib}$ such that a and b are integers. The norm ${\displaystyle 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}$ and ${\displaystyle p=2.}$ The last case is not considered in Fermat's statement, but is trivial, as ${\displaystyle 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 ${\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 element in ${\displaystyle {\mathcal{O}}_{\sqrt{d}},}$ or the ideal norm of an ideal of ${\displaystyle {\mathcal{O}}_{\sqrt{d}},}$ which is necessarily prime. Moreover, the law of quadratic reciprocity allows distinguishing the two cases in terms of congruences. If ${\displaystyle {\mathcal{O}}_{\sqrt{d}}}$ is a principal ideal domain, then p is an ideal norm if and only

${\displaystyle 4p=a^2-d{b}^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}$ and ${\displaystyle d=-3.}$ If p is an odd prime, then

${\displaystyle p=x^2+2y^2⟺p\equiv 1\text{ or }p\equiv 3(\mathrm{mod}8),}$

${\displaystyle p=x^2+3y^2⟺p\equiv 1(\mathrm{mod}3).}$

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 p, q are of the form 20k + 3 or 20k + 7, then pq = x² + 5y². Euler later extended this to the conjecture that

${\displaystyle p=x^2+5y^2⟺p\equiv 1\text{ or }p\equiv 9(\mathrm{mod}20),}$

${\displaystyle 2p=x^2+5y^2⟺p\equiv 3\text{ or }p\equiv 7(\mathrm{mod}20).}$

Both Fermat's assertion and Euler's conjecture were established by Joseph-Louis Lagrange. This more complicated formulation relies on the fact that ${\displaystyle {\mathcal{O}}_{\sqrt{-5}}}$ is not a principal ideal domain, unlike ${\displaystyle {\mathcal{O}}_{\sqrt{-2}}}$ and ${\displaystyle {\mathcal{O}}_{\sqrt{-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 1\le n<\sqrt{p}}$, test whether the square root of ${\displaystyle p-n^2}$ is an integer. If this is 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).

Description

Given an odd prime ${\displaystyle p}$ in the form ${\displaystyle 4k+1}$, first find ${\displaystyle x}$ such that ${\displaystyle x^2\equiv -1(\mathrm{mod}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}}(\mathrm{mod}p)}$.

Such an ${\displaystyle x}$ will satisfy the condition since quadratic non-residues satisfy ${\displaystyle q^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}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(\mathrm{mod}97)}$. so we let ${\displaystyle x={13}^{\frac{97-1}{4}}=22(\mathrm{mod}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). 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. And more recently Christopher gave a partition-theoretic proof.

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. 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 and do not correspond exactly to the four steps below. The fifth step below is from the second paper.

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=q{p}_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.

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/2}$: indeed, when ${\displaystyle q>2}$ is even, gcd${\displaystyle (a,q/2)=1}$; otherwise since gcd${\displaystyle (a,q/2)\mid q/2\mid q\mid a^2+b^2}$, we would also have gcd${\displaystyle (a,q/2)\mid b}$.

Multiplying out we obtain

${\displaystyle 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 ${\displaystyle A}$. Since ${\displaystyle q}$ divides both ends of this equation sequence it follows that ${\displaystyle c^2+d^2}$ must also be divisible by ${\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 g^2}$ divides ${\displaystyle r}$, so writing ${\displaystyle e=c/g}$, ${\displaystyle f=d/g}$ and ${\displaystyle s=r/g^2}$, we obtain the expression ${\displaystyle e^2+f^2=qs}$ for relatively prime ${\displaystyle e}$ and ${\displaystyle f}$, and with ${\displaystyle s<q/2}$, since

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

Now finally, the descent step: if ${\displaystyle q}$ is not the sum of two squares, then by step (3.) there must be a factor ${\displaystyle q_1}$ say of ${\displaystyle s}$ which is not the sum of two squares. But ${\displaystyle q_1\le s<q/2<q}$ and so repeating these steps (initially with ${\displaystyle e,f;q_1}$ in place of ${\displaystyle a,b;q}$, and so on ad infinitum) we shall be able to find a strictly decreasing infinite sequence ${\displaystyle q,q_1,q_2,\dots }$ of positive integers which are not themselves the sums of two squares but which divide into a sum of two 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.

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

If ${\displaystyle p=4n+1}$, then by Fermat's Little Theorem each of the numbers ${\displaystyle 1,2^{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 as

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

Since ${\displaystyle p}$ is prime, it must divide one of the two factors. If in any of the ${\displaystyle 4n-1}$ cases it divides the first factor, then by the previous step we conclude that ${\displaystyle p}$ is itself a sum of two squares (since ${\displaystyle a}$ and ${\displaystyle b}$ differ by ${\displaystyle 1}$, they are relatively prime). So it is enough to show that ${\displaystyle p}$ cannot always divide the second factor. If it divides all ${\displaystyle 4n-1}$ differences ${\displaystyle 2^{2n}-1,3^{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 so forth. Since the ${\displaystyle k}$th differences of the sequence ${\displaystyle 1^k,2^k,3^k,\dots }$ are all equal to ${\displaystyle k!}$ (Finite difference), the ${\displaystyle 2n}$th differences would all be constant and equal to ${\displaystyle (2n)!}$, which is certainly not divisible by ${\displaystyle p}$. Therefore, ${\displaystyle p}$ cannot divide all the second factors which proves that ${\displaystyle p}$ is indeed the sum of two squares.

Lagrange's proof through quadratic forms

Lagrange completed a proof in 1775 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 a{x}^2+bxy+c{y}^2}$ 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=a{x}^2+bxy+c{y}^2}$. Fermat's theorem on sums of two squares is then equivalent to the statement that a prime ${\displaystyle p}$ is represented by the form ${\displaystyle x^2+y^2}$ (i.e., ${\displaystyle a=c=1}$, ${\displaystyle b=0}$) exactly when ${\displaystyle p}$ is congruent to ${\displaystyle 1}$ modulo ${\displaystyle 4}$.

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

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

${\displaystyle x=\alpha x^{\prime }+\beta y^{\prime }}$

${\displaystyle y=\gamma x^{\prime }+\delta y^{\prime }}$

with ${\displaystyle \alpha \delta -\beta \gamma =\pm 1}$ such that, when substituted into the first form, yield the second. Equivalent forms are readily seen to have the same discriminant, and hence also 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 represent exactly the same integers, because these kind of substitutions can be reversed by substitutions of the same kind.

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

${\displaystyle p{x}^2+2mxy+\left(\frac{m^2+1}{p}\right)y^2,}$

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

We claim such a square root of ${\displaystyle -1}$ is given by ${\displaystyle K=\prod _{k=1}^{\frac{p-1}{2}}k}$. Firstly it follows from Euclid's Fundamental Theorem of Arithmetic that ${\displaystyle ab\equiv 0(\mathrm{mod}p)⟺a\equiv 0(\mathrm{mod}p)\text{or}b\equiv 0(\mathrm{mod}p)}$. Consequently, ${\displaystyle a^2\equiv 1(\mathrm{mod}p)⟺a\equiv \pm 1(\mathrm{mod}p)}$: that is, ${\displaystyle \pm 1}$ are their own inverses modulo ${\displaystyle p}$ and this property is unique to them. It then follows from the validity of Euclidean division in the integers, and the fact that ${\displaystyle p}$ is prime, that for every ${\displaystyle 2\le a\le 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}\ne a}$ of ${\displaystyle a}$ modulo ${\displaystyle p}$. In particular therefore the product of all non-zero residues modulo ${\displaystyle p}$ is ${\displaystyle -1}$. Let ${\displaystyle L=\prod _{l=\frac{p+1}{2}}^{p-1}l}$: from what has just been observed, ${\displaystyle KL\equiv -1(\mathrm{mod}p)}$. But by definition, since each term in ${\displaystyle K}$ may be paired with its negative in ${\displaystyle L}$, ${\displaystyle L=(-1{)}^{\frac{p-1}{2}}K}$, which since ${\displaystyle p}$ is odd shows that ${\displaystyle K^2\equiv -1(\mathrm{mod}p)⟺p\equiv 1(\mathrm{mod}4)}$, as required.

Dedekind's two proofs using Gaussian integers

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

1. First proof. If ${\displaystyle p}$ is an odd prime number, 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 x^p+y^p{i}^p\equiv x+(-1{)}^{\frac{p-1}{2}}yi(\mathrm{mod}p),}$

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

Kummer had already established that if f ∈ {1,2} is the order of the Frobenius automorphism of Z[i]/(p), 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 result for any extension of Z obtained by adjoining a primitive m-th root of unity, where m was any positive integer; this is the case m = 4 of that result.) 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^2+y^2}$, 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 one of the ideal factors of (p) must be a strict divisor of ${\displaystyle N(p)=p^2}$, so that we must have ${\displaystyle p=N(\alpha )=N(a+bi)=a^2+b^2}$, which gives Fermat's theorem.

2. Second proof. This proof builds on Lagrange's result that if ${\displaystyle p=4n+1}$ is a prime number, then there must be an integer m such that ${\displaystyle m^2+1}$ is divisible by p (we can also see this by Euler's criterion); it 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}$ (as it does not divide their imaginary parts), but it does divide their product ${\displaystyle m^2+1}$, it follows that ${\displaystyle p}$ cannot be a prime 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 have only two factors (since the norm is multiplicative, and ${\displaystyle p^2=N(p)}$, there can only be up to two factors of p), so it must be 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's Theorem

For ${\displaystyle p}$ congruent to ${\displaystyle 1}$ mod ${\displaystyle 4}$ a prime, ${\displaystyle -1}$ is a quadratic residue mod ${\displaystyle p}$ by Euler's criterion. Therefore, there exists an integer ${\displaystyle m}$ such that ${\displaystyle p}$ divides ${\displaystyle m^2+1}$. Let ${\displaystyle \hat{i},\hat{j}}$ be the standard basis elements for the vector space ${\displaystyle {\mathbb{R}}^2}$ and set ${\displaystyle \overrightarrow{u}=\hat{i}+m\hat{j}}$ and ${\displaystyle \overrightarrow{v}=0\hat{i}+p\hat{j}}$. Consider the lattice ${\displaystyle S=\{a\overrightarrow{u}+b\overrightarrow{v}\mid a,b\in \mathbb{Z}\}}$. If ${\displaystyle \overrightarrow{w}=a\overrightarrow{u}+b\overrightarrow{v}=a\hat{i}+(am+bp)\hat{j}\in S}$ then ${\displaystyle \Vert \overrightarrow{w}{\Vert }^2\equiv a^2+(am+bp{)}^2\equiv a^2(1+m^2)\equiv 0(\mathrm{mod}p)}$. Thus ${\displaystyle p}$ divides ${\displaystyle \Vert \overrightarrow{w}{\Vert }^2}$ for any ${\displaystyle \overrightarrow{w}\in S}$.

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

Zagier's "one-sentence proof"

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

${\displaystyle (x,y,z)\mapsto \{\begin{array}{l}(x+2z,z,y-x-z),\text{if}x<y-z\\ (2y-x,y,x-y+z),\text{if}y-z<x<2y\\ (x-2y,x-y+z,y),\text{if}x>2y\end{array}}$

which has exactly one fixed point ${\displaystyle (1,1,k)}$. This proves that the cardinality of ${\displaystyle S}$ is odd. Hence, ${\displaystyle 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 years? (Fermat's two square theorem) on YouTube.

Proof with partition theory

In 2016, A. David Christopher gave a partition-theoretic proof by considering partitions of the odd prime ${\displaystyle n}$ having exactly two sizes ${\displaystyle a_i(i=1,2)}$, each occurring exactly ${\displaystyle a_i}$ times, and by showing that at least one such partition exists if ${\displaystyle n}$ is congruent to 1 modulo 4.

Left communism

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Left_communism

 

Left communism, or the communist left, is a position held by the left wing of communism, which criticises the political ideas and practices espoused by Marxist–Leninists and social democrats. Left communists assert positions which they regard as more authentically Marxist than the views of Marxism–Leninism espoused by the Communist International after its Bolshevization by Joseph Stalin and during its second congress.

In general, there are two currents of left communism, namely the Italian and Dutch–German left. The communist left in Italy was formed during World War I in organizations like the Italian Socialist Party and the Communist Party of Italy. The Italian left considers itself to be Leninist in nature, but denounces Marxism–Leninism as a form of bourgeois opportunism materialized in the Soviet Union under Stalin. The Italian left is currently embodied in organizations such as the Internationalist Communist Party and the International Communist Party. The Dutch–German left split from Vladimir Lenin prior to Stalin's rule and supports a firmly council communist and libertarian Marxist viewpoint as opposed to the Italian left which emphasised the need for an international revolutionary party.

Left communism differs from most other forms of Marxism in believing that communists should not participate in bourgeois parliaments, and some argue against participating in conservative trade unions. However, many left communists split over their criticism of the Bolsheviks. Council communists criticised the Bolsheviks for elitist party functions and emphasised a more autonomous organisation of the working class, without political parties.

Although she was murdered in 1919 before left communism became a distinct tendency, Rosa Luxemburg has been heavily influential for most left communists, both politically and theoretically. Proponents of left communism have included Herman Gorter, Antonie Pannekoek, Otto Rühle, Karl Korsch, Amadeo Bordiga and Paul Mattick. Other proponents of left communism have included Onorato Damen, Jacques Camatte, and Sylvia Pankhurst. Later prominent theorists are shared with other tendencies such as Antonio Negri, a founding theorist of the autonomist tendency.

Early history and overview

Two major traditions can be observed within left communism, namely the Dutch–German current and the Italian current. The political positions those traditions share are opposition to popular fronts, to many kinds of nationalism and national liberation movements and to parliamentarianism.

The historical origins of left communism come from World War I. Most left communists are supportive of the October Revolution in Russia, but retain a critical view of its development. However, some in the Dutch–German current would in later years come to reject the idea that the revolution had a proletarian or socialist nature, arguing that it had simply carried out the tasks of the bourgeois revolution by creating a state capitalist system.

Left communism first came into focus as a distinct movement around 1918. Its essential features were a stress on the need to build a communist party or workers' council entirely separate from the reformist and centrist elements who "betrayed the proletariat", opposition to all but the most restricted participation in elections and an emphasis on militancy. Apart from this, there was little in common between the two wings. Only the Italians accepted the need for electoral work at all for a very short period of time which they later vehemently opposed, attracting criticism from Vladimir Lenin in "Left-Wing" Communism: An Infantile Disorder.

Russian left communism

Left Bolshevism emerged in 1907 as the Vpered group challenged Vladimir Lenin's perceived authoritarianism and parliamentarianism. The group included Alexander Bogdanov, Maxim Gorky, Anatoly Lunacharsky, Mikhail Pokrovsky, Grigory Aleksinsky, Stanislav Volski and Martyn Liadov. The Otzovists, or Recallists, advocated the recall of RSDLP representatives from the Third Duma. Bogdanov and his allies accused Lenin and his partisans of promoting liberal democracy through "parliamentarism at any price".

In 1918, a faction known as the Left Communists (or the Left Bolsheviks) emerged within the Russian Communist Party. It opposed a separate peace treaty with the Central Powers of World War I, held radical views on economic and social policy (including cultural, educational, and family policy) and on military organization, and opposed national self-determination. Its members included Andrei Bubnov, Nikolai Bukharin, Alexandra Kollontai, Valerian Osinsky, Georgy Pyatakov, Yevgeni Preobrazhensky, Karl Radek, and Vladimir Smirnov. After the Treaty of Brest-Litovsk was signed in March 1918, the Left Bolsheviks continued to criticize the "pragmatism" and "conservatism" of Lenin and his allies, urging immediate nationalization of industry, workers' control, and no compromise with capitalist forces.

The faction largely died out by the end of 1918, as its leaders accepted that much of their program was unrealistic under the circumstances of the Russian Civil War and as the policies of War Communism satisfied their demands for a radical transformation of the economy. The Military Opposition and the Workers' Opposition inherited some characteristics and members of the Left Bolsheviks, as did Gavril Myasnikov's Workers Group of the Russian Communist Party during the debates on the New Economic Policy and the succession to Lenin. Most Left Bolsheviks were affiliated with the Left Opposition in the 1920s, and were expelled from the party in 1927 and later killed during Joseph Stalin's Great Purge.

Dutch–German left communism until 1933

Further information: Left Communists (Weimar Republic)

Left communism emerged in both countries together and was always very closely connected. Among the leading theoreticians of the more powerful German movement were Antonie Pannekoek and Herman Gorter and German activists found refuge in the Netherlands after the Nazis came to power in 1933. The critique of social democratic reformism can be traced back before World War I since in the Netherlands a revolutionary wing of social democracy had broken from the reformist party even before the war and had built links with German activists. By 1915, the Antinational Socialist Party was founded by Franz Pfemfert and was linked to Die Aktion. After the beginning of the German Revolution in 1918, a leftist mood could be found among sections of the communist parties of both countries. In Germany, this led directly to the foundation of the Communist Workers Party of Germany (KAPD) after its leading figures were expelled from the Communist Party of Germany (KPD) by Paul Levi. This development was mirrored in the Netherlands and on a smaller scale in Bulgaria, where the left communist movement was to mimic that of Germany.

When it was founded, the KAPD included some tens of thousands of revolutionaries. However, it had broken up and practically dissolved within a few years. This was because it was founded on the basis of revolutionary optimism and a purism that rejected what became known as frontism. Frontism entailed working in the same organisations as reformist workers. Such work was seen by the KAPD as unhelpful at a time when the revolution was thought to be an imminent event and not merely a goal to be aimed at. This led the members of the KAPD to reject working in the traditional trade unions in favour of forming their own revolutionary unions. These unionen, so called to distinguish them from the official trade unions, had 80,000 members in 1920 and peaked in 1921 with 200,000 members, after which they declined rapidly. They were also organisationally divided from the beginning, with those unionen linked to the KAPD forming the AAU-D and those in Saxony around Otto Rühle who opposed the conception of a party in favour of a unitary class organisation being organised as the AAU-E.

The KAPD was unable to reach even its founding congress prior to suffering its first split when the so-called National Bolshevik tendency around Fritz Wolffheim and Heinrich Laufenberg appeared (this tendency has no connection with modern political tendencies in Russia which use the same name). More seriously, the KAPD lost most of its support very rapidly as it failed to develop lasting structures. This also contributed to internecine quarrels and the party actually split into two competing tendencies known as the Essen and Berlin tendencies to the historians of the left. The recently established Communist Workers International (KAI) split on exactly the same lines as did the tiny Communist Workers Party of Bulgaria. The only other affiliates of the KAI were the Communist Workers Party of Britain led by Sylvia Pankhurst, the Communist Workers Party of the Netherlands (KAPN) in the Netherlands and a group in Russia. The AAU-D split on the same lines and it rapidly ceased to exist as a real tendency within the factories.

Left communism and the Communist International

Left communists generally supported the Bolshevik seizure of power in October 1917 and entertained enormous hopes in the founding of the Communist International, or Comintern. In fact, they controlled the first body formed by the Comintern to coordinate its activities in Western Europe, the Amsterdam Bureau. However, this was little more than a very brief interlude and the Amsterdam Bureau never functioned as a leadership body for Western Europe as was originally intended. The Vienna Bureau of the Comintern may also be classified as left communist, but its personnel were not to evolve into either of the two historic currents that made up left communism. Rather, the Vienna Bureau adopted the ultra-left ideas of the earliest period in the history of the Comintern.

Left communists supported the Russian Revolution, but did not accept the methods of the Bolsheviks. Many of the Dutch–German tradition adopted Rosa Luxemburg's criticism as outlined in her posthumously published essay entitled The Russian Revolution. In this essay, she rejected the Bolshevik position on distribution of land to the peasantry and their espousal of the right of nations to self-determination which she rejected as historically outmoded. The Italian left communists did not at the time accept any of these criticisms and both currents would evolve.

To a considerable degree, Lenin's well known polemic Left-Wing Communism: An Infantile Disorder is an attack on the ideas of the emerging left communist currents. His main aim was to polemicise with currents moving towards pure revolutionary tactics by showing them that they could remain based on firmly revolutionary principles while utilising a variety of tactics. Therefore, Lenin defended the use of parliamentarism and working within the official trade unions.

As the Kronstadt rebellion occurred at a time when the debate on tactics was still raging within the Comintern, it has been wrongly seen as being left communist by some commentators. In fact, the left communist currents had no connection with the rebellion, although they did rally to its support when they learned of it. In later years, the German–Dutch tradition in particular would come to see the suppression of the revolt as the historic turning point in the evolution of the Russian state after October 1917.

1939–1945

Many small currents to the left of the mass communist parties collapsed at the beginning of World War II and the left communists were initially silent too. Despite having foreseen the war more clearly than some other factions, when it began they were overwhelmed. Many were persecuted by either German Nazism or Italian fascism. Leading militants of the communist left such as Mitchell, who was Jewish, were to die in the Buchenwald concentration camp.

Meanwhile, the final council communist groups in Germany had disappeared in the maelstrom and the International Communist Group (GIK) in the Netherlands was moribund. The former centrist group led by Henk Sneevliet (the Revolutionary Socialist Workers Party, RSAP) transformed itself into the Marx–Lenin–Luxemburg Front. In April 1942, its leadership was arrested by the Gestapo and killed. The remaining activists then split into two camps as some turned to Trotskyism forming the Committee of Revolutionary Marxists (CRM) while the majority formed the CommunistenBond-Spartacus. The latter group turned to council communism and was joined by most members of the GIK.

In 1941, the Italian fraction was reorganised in France and along with the new French Nucleus of the Communist Left came into conflict with the ideas which the fraction had propagated from 1936, namely of the social disappearance of the proletariat and localised wars and so on. These ideas continued to be defended by Vercesi in Brussels. Gradually, the left fractions adopted positions drawn from German left communism. They abandoned the conception that the Russian state remained in some way proletarian and also dropped Vercesi's conception of localised wars in favour of ideas on imperialism inspired by Rosa Luxemburg. Vercesi's participation in a Red Cross committee was also fiercely contested.

The strike at FIAT in October 1942 had a huge impact on the Italian fraction, which was deepened by the fall of Mussolini's regime in July 1943. The Italian fraction now saw a pre-revolutionary situation opening in Italy and prepared to participate in the coming revolution. In 1943 the Internationalist Communist Party was founded by Onorato Damen and Luciano Stefanini, amongst others. By 1945 the party had 5,000 members all over Italy with some supporters in France, Belgium and the US. It published a Manifesto of the Communist Left to the European Proletariat, which called upon workers to put class war before national war.

In France, revived by Marco in Marseilles, the Italian fraction now worked closely with the new French fraction, which was formally founded in Paris in December 1944. However, in May 1945 the Italian fraction, many of whose members had already returned to Italy, voted to dissolve itself so that its militants could integrate themselves as individuals into the Internationalist Communist Party. The conference at which this decision was made also refused to recognise the French fraction and expelled Marco from their group.

This led to a split in the French fraction and the formation of the Gauche Communiste de France (GCF) by the French fraction led by Marco. The history of the GCF belongs to the post-war period. Meanwhile, the former members of the French fraction who sympathised with Vercesi and the Internationalist Communist Party formed a new French fraction which published the journal L'Etincelle and was joined at the end of 1945 by the old minority of the fraction who had joined L'Union Communiste in the 1930s.

One other development during the war years merits mention at this point. A small grouping of German and Austrian militants came close to left communist positions in these years. Best known as the Revolutionary Communist Organisation, these young militants were exiles from Nazism living in France at the start of World War II and were members of the Trotskyist movement but they had opposed the formation of the Fourth International in 1938 on the grounds that it was premature. They were refused full delegates' credentials and only admitted to the founding conference of the Youth International on the following day. They then joined Hugo Oehler's International Contact Commission for the Fourth (Communist) International and in 1939 were publishing Der Marxist in Antwerp.

With the beginning of the war, they took the name Revolutionary Communists of Germany (RKD) and came to define Russia as state capitalist in agreement with Ante Ciliga's book The Russian Enigma. At this point, they adopted a revolutionary defeatist position on the war and condemned Trotskyism for its critical defence of Russia (which was seen by Trotskyists as a degenerated workers' state). After the fall of France, they renewed contact with militants in the Trotskyist milieu in Southern France and recruited some of them into the Communistes Revolutionnaires (CR) in 1942. This group became known as Fraternisation Proletarienne in 1943 and then L'Organisation Communiste Revolutionnaire in 1944. The CR and RKD were autonomous and clandestine, but worked closely together with shared politics. As the war ran its course, they evolved in a councilist direction while also identifying more and more with Luxemburg's work. They also worked with the French Fraction of the Communist Left and seem to have disintegrated at the end of the war. This disintegration was sped no doubt by the capture of leading militant Karl Fischer, who was sent to the Buchenwald concentration camp where he was to participate in writing the Declaration of the Internationalist Communists of Buchenwald when the camp was liberated.

1952–1968

See also: Left communism in China and Shengwulian

The year 1952 signalled the end of mass influence on the part of Italian left communism as its sole remaining representative, the Internationalist Communist Party, split in two sections: the group led by Bordiga took the name International Communist Party, while the group around Damen retained the name Internationalist Communist Party. The Gauche Communiste de France (GCF) dissolved in the same year. Left communists entered a period of almost constant decline from this point onwards, although they were somewhat rejuvenated by the events of 1968.

Examples of left communism ideological currents existed in China during the Great Proletarian Cultural Revolution (GPCR). For example, the Hunan rebel group the Shengwulian argued for "smashing" the existing state apparatus and establishing a "People's Commune of China" based on the democratic ideals of the Paris Commune.

Since 1968

The uprisings of May 1968 led to a large resurgence of interest in left communist ideas in France where various groups were formed and published journals regularly until the late 1980s when the interest started to fade. A tendency called communization was invented in the early 1970s by French left communists, synthesizing different currents of left communism. It remains influential in libertarian marxist and left communist circles today. Outside of France, various small left communist groups emerged, predominantly in the leading capitalist countries. In the late 1970s and early 1980s the Internationalist Communist Party initiated a series of conferences of the communist left to engage those new elements, also attended by the International Communist Current. As a result of these, in 1983 the International Bureau for the Revolutionary Party (later renamed as the Internationalist Communist Tendency) was established by the Internationalist Communist Party and the British Communist Workers Organisation.

Prominent post-1968 proponents of left communism have included Paul Mattick and Maximilien Rubel. Prominent left communist groups existing today include the International Communist Party, the International Communist Current and the Internationalist Communist Tendency. In addition to the left communist groups in the direct lineage of the Italian and Dutch traditions, a number of groups with similar positions have flourished since 1968, such as the workerist and autonomist movements in Italy; Kolinko, Kurasje, Wildcat; Subversion and Aufheben in England; Théorie Communiste, Echanges et Mouvements and Démocratie Communiste in France; TPTG and Blaumachen in Greece; Kamunist Kranti in India; and Collective Action Notes and Loren Goldner in the United States.