Fermat's Two Square Theorem: How do you prove that an odd prime is the sum of two squares iff it is congruent to 1 mod 4?

Question

It is a theorem in elementary number theory that if $p$ is a prime and congruent to 1 mod 4, then it is the sum of two squares. Apparently there is a trick involving arithmetic in the gaussian integers that lets you prove this quickly. Can anyone explain it?

Answer 1

Let $p$ be a prime congruent to 1 mod 4. Then to write $p = x^2 + y^2$ for $x,y$ integers is the same as writing $p = (x+iy)(x-iy) = N(x+iy)$ for $N$ the norm.

It is well-known that the ring of Gaussian integers $\mathbb{Z}[i]$ is a principal ideal domain, even a euclidean domain. Now I claim that $p$ is not prime in $\mathbb{Z}[i]$. To determine how a prime $p$ of $\mathbb{Z}$ splits in $\mathbb{Z}[i]$ is equivalent to determining how the polynomial $X^2+1$ splits modulo $p$.

First off, $-1$ is a quadratic residue modulo $p$ because $p \equiv 1 \mod 4$. Consequently, there is $t \in \mathbb{Z}$ with $t^2 \equiv -1 \mod p$, so $X^2+1$ splits modulo $p$, and $p$ does not remain prime in $\mathbb{Z}[i]$. (Another way of seeing this is to note that if $p$ remained prime, then we'd have $p \mid (t+i)(t-i)$, which means that $p \mid t+i$ or $t \mid t-i$.)

Anyway, as a result there is a non-unit $x+iy$ of $\mathbb{Z}[i]$ that properly divides $p$. This means that the norms properly divide as well. In particular, $N(x+iy) = x^2+y^2$ properly divides $p^2$, so is $p$ or $1$. It cannot be the latter since otherwise $x+iy$ would be a unit. So $x^2+y^2 = p$.

Answer 2

Perhaps my favorite argument (other than any arguably "correct" arguments, such as the one Akhil has given, or arguments starting from the fact that $x^2 + y^2$ is the unique binary quadratic form of discriminant $-4$ up to equivalence) uses continued fractions. Suppose that $u^2 \equiv -1 \pmod{p}$, and consider the continued fraction expansion of the rational number $u/p$. Let $r/s$ be the last convergent to $u/p$ with the property that $s < \sqrt{p}$. Then, setting $x=s$ and $y = rp-us$, one has $x^2 + y^2 = p$.

Here's the argument: let $r'/s'$ be the convergent following $r/s$. Then the basic theory of continued fractions gives the estimate $|r/s - u/p| < 1/ss'$, and the right-hand side is less than $1/s\sqrt{p}$ by hypothesis. Clearing denominators gives $y < \sqrt{p}$, so that $0 < x^2 + y^2 < 2p$. On the other hand $x^2 + y^2$ is checked to be divisible by $p$ (by choice of $u$), so must be equal to $p$.

Answer 3

Here is another proof without complex numbers.

We start with proving that there exists $z \in \mathbb{N}$ such that $z^2 + 1 \equiv 0 \pmod p$. We do this in the same way as Akhil Mathew.

Let we have $a^2 + b^2 = pm$. Take $x$ and $y$ such that
$x \equiv a \pmod m$ and
$y \equiv b \pmod m$ and
$x, y \in [-m/2, m/2)$.

Consider $u = ax + by$ and $v = ay - bx$. Then $u^2 + v^2 = (a^2 + b^2)(x^2 + y^2)$. Moreover, $u$ and $v$ are multiples of $m$. Hence $(u/m)^2 + (v/m)^2 = p (x^2 + y^2)/m$. $(x^2 + y^2)/m$ is an integer because of the definition of $x$ and $y$ and that $a^2 + b^2 = pm$.
Also $(x^2 + y^2)/m$ is less than $m/2$.

Now we change $a$ by $u$ and $b$ by $v$ and continue this process until we get $m=1$.

Notice that this is quite efficient way to find representation of $p$ as a sum of two squares - it takes $O(\log p)$ steps to find it provided we have found $z$ such that $z^2 + 1$ is multiple of $p$.

Answer 4

There is an amazing proof of this due to Don Zagier : one-sentence proof.

Answer 5

Taken From I.N. Herstein There are 2 results which i am going to use.

1. Let $p$ be a prime integer and suppose that for some integer $c$ relatively prime to $p$ we can find integers $x$ and $y$ such that $x^{2}+y^{2}=cp$. Then $p$ can be written as the sum of 2 squares.

2. If $p$ is a prime of the form $4n+1$, then we can solve the congruence $x^{2} \equiv \ -1 \ (mod) \ p$.

Now the main result. If $p$ is a prime of the form $4n+1$ then $p$ is the sum of 2 squares.

Proof. By 2 there exists and $x$ such that $x^{2} \equiv -1 \text{mod} \ p$. So $x$ can be chose such that $0 \leq x \leq (p-1)$. We can restrict the size of $p$ even further, namely to satisfy $|x| \leq \frac{p}{2}$. For if $x > p/2$ then, $y=p-x$ satisfies $y^{2} \equiv -1 \text{mod} \ p$ but $|y| \leq p/2$. Thus we may assume that we have an integer $x$ such that $|x| \leq p/2$ and $x^{2}+1$ is a multiple of $p$ say $cp$. Now $cp=x^{2}+1 \leq p^{2}/4 +1 < p^{2}$, hence $c < p$ and hence $(c,p)=1$. Invoking (1) we have $p=a^{2}+b^{2}$.

Answer 6

Let $$\Psi(n,m,k)=100n^2+20nm+m^2+4k^2$$

be a prime number for some $(n,m,k)$

Then:

This combination of $(n,m,k)$ must not share any factors. Except $(n,m)$ can share factors as long as: $$\gcd(n,m,k) = 1$$ So:

$$p = (10n+m)^2+(2k)^2$$

For the expression above to be a prime number, a combination of $(x,y)$ must be either even-odd or odd-even. But it already is for the $(n,m,k)$ we have picked.

If we pick n as some natural number, k as some positive natural number and m = 1,3,5,7,9 we fit the definition given above. Now we can expand and see that:

$$p = 100n^2+20nm+m^2+4k^2$$

This means $m^2\equiv1(mod4)$ since all other terms in the equation are already are congurent to $0(mod4)$.

But if you haven't already noticed for the choice for all of the m's we've picked all happen to be congurent to $1(mod4)$ when squared.

This means whether or not p is prime doesn't matter this equation will always produce a result of the form $p=4a+1$

Now this result may not give prime numbers all the time obviously. But our choice of $(n,m,k)$ was already for some, not all. Then one can state that:

If our choice of $(n,m,k)$ produces a prime number then it is a solution.

Except for the case $$1^2+1^2 = 2$$ which is the only case that will refute this, so it can be ignored.

Thus for:

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

if p is prime then:

$$p\equiv 1(mod4)$$

EDIT: The proof above isn't fully satisfactory since I start with $p=x^2+y^2$.

If we start backwards by assuming:

$$p \equiv 1(mod4)$$

Then

$$p = 4n+1$$

Now consider the following:

$$p=4n+1=100a^2+20ab+b^2+4c^2$$

If $10+b$ is odd then we don't have anything to worry about. So we have a look at $b^2$ and again $b = 1,3,5,7,9$ so:

$$b^2 \equiv 1(mod4)$$

or:

$$b^2 = 4m+1$$

Then we have:

$$p=4m+100a^2+20a(4m+1)+4c^2+1$$

So we have written $p$ as a sum of two squares:

$$p=(10a+4m+1)^2+(2c)^2$$

since one can say $x= 10a+4m+1$ and $y = 2c$.

So now I have shown that either way around the statement holds.

Infact this is related to Zagier's proof since if we let $y = c$ instead:

$$p=x^2+(2y)^2$$

Thus now we have shown if:

$$p \equiv 1(mod4)$$

then:

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

So now one can say that a prime number can be written as a sum of two squares iff $p \equiv 1(mod4)$

Also we know this is the only way besides the case $1^2+1^2=2$ to write primes as a sum of two squares because of the first argument where I said the combination of (x,y) must be even-odd or odd-even. And we know we can write ANY prime number of the form $4a+1$ as a sum of two squares because $\Psi(n,m,k)$ for the given limitations on $(n,m,k)$ can produce any odd natural number of the form $4a+1$. And since the set that represents all natural numbers of the form $4a+1$ includes the set of primes that can be written as $4a+1$.

Please let me know if there is any problems with the proof.

Answer 7

Let $p \equiv 1\ (\text {mod}\ 4)$ and $a = \left (\frac {p-1} {2} \right )!$. Observe that $a^2 \equiv -1\ (\text {mod}\ p)$ by Wilson's theorem. Consider an ideal $I$ of $\Bbb Z[i]$ such that $I = \langle p,i-a \rangle$. Observe that $I \cap \Bbb Z = p \Bbb Z$. Let $R = \Bbb Z[i]/I$. Then $R$ is a commutative ring with identity. Consider the map $f : \Bbb Z \longrightarrow R$ such that $1 \mapsto 1_R$, where $1_R$ is the multiplicative identity in $R$ and extend it to a homomorphism. Observe that $f$ is surjective and $ker (f) = p \Bbb Z$. So by the first isomorphism theorem we have $\Bbb Z/p \Bbb Z \cong R$. Since $\Bbb Z[i]$ is a PID $\exists$ $a+ib \in \Bbb Z[i]$ such that $I = \langle a+ib \rangle$. Observe that $|R| = |\Bbb Z[i]/\langle a+ib \rangle| = a^2+b^2$. So we have $p = |\Bbb Z/p\Bbb Z| = a^2 + b^2,$ as claimed.

Answer 8

I tried this via Wilson's theorem- It seems to work but would be grateful if someone could verify it/offer improvements?

Suppose a prime $p=1 \ \text{mod} 4 $. By Wilson's theorem, $ (p-1)! = -1 (\ \text{mod} p) $.

But $ p-r = -r (\text{mod} p) $

So $ -1= 1 (p-1) 2 (p-1)...( \frac{p-1}{2})( \frac{p-1}{2} ) = 1 (-1) 2(-2)...( \frac{p-1}{2})( \frac{p-1}{2} )= (-1)^{ \frac{p-1}{2}}(( \dfrac{p-1}{2})!)^{2} \ ( \text{mod} p) $

$ (-1)^{ \frac{p-1}{2}}= (-1)^{ \frac{4k+1-1}{2}}=1 $ so $ -1 =( \dfrac{p-1}{2})!)^{2} \ ( \text{mod} p) $

In other words $np = 1 + (( \dfrac{p-1}{2})!)^{2} $ iff $p=1 \ \text{mod} 4 $.

Any integer $x^{2} = 0,1 \ \text{mod} 4 $ so we cant find an $x^2, y^2$ such that $x^2+y^2 = 3 \ \text{mod} 4$. As a prime is odd, it is either congruent to 1 or 3 mod 4 so it can only be written as a sum of 2 squares if congruent to 1 mod4.

Answer 9

To answer the title: along with the standard Gaussian integers proof of the backwards direction, the forwards direction is simple: (We exclude the case of the only even prime $2 = 1^2 + 1^2$)

An odd prime is congruent to 1 or 3 mod 4, and since 0 and 1 are the only quadratic residues mod 4, we must have the prime congruent to 1 mod 4.

Alternatively: observe $p$ is coprime to $a$ and $b$ since if $p \mid a$ then $p \mid b$ and vice versa, then $p^2 \mid a^2,b^2 \implies p \mid a^2 + b^2 \implies p^2 \mid p$, a contradiction.

From $a^2 + b^2 \equiv 0 \iff a^2 \equiv -b^2 \iff (ab^{-1})^2 \equiv -1 \mod p$, $-1$ is a quadratic residue only if $p \equiv 1 \mod 4$.

Answer 10

See Geometrical figure explanation of Zagier's one-sentence proof:

See details explanation given By mathologer on his you tube video

Answer 11

Let $p=a^2+b^2$ be an odd prime. Since $p$ is odd, $a$ and $b$ can't both be even, nor can they both be odd. So, one of them is odd, and one is even. Without Loss of Generality, let $a=2k+1$ be odd, and $b=2l$ be even. Then $$p=a^2+b^2=(2k+1)^2+(2l)^2=4(k^2+k+l^2)+1.$$ So clearly, $p\equiv 1\pmod{4}$.

Now, suppose $p\equiv 1\pmod{4}$ is prime, we will show that there exist integers $a$ and $b$ such that $p=a^2+b^2$. Since $p\equiv 1\pmod{4}$, we have $p=4k+1$. First, we claim that their exists some $\alpha\in\mathbb{Z}$ such that $p\mid\alpha^2+1$. Note that $$\genfrac{(}{)}{}{}{-1}{p}=(-1)^{\frac{p-1}{2}}=(-1)^{2k}=1.$$

So $-1$ is a quadratic residue (mod $p$), and there exists $\alpha$ such that $\alpha^2\equiv -1\pmod{p}$ or $p\mid\alpha^2+1$. Clearly $p\nmid a$, otherwise $a^2+1\equiv 1\pmod{p}$. Now, let $x$ and $y$ range over all the numbers $0,1,2,\dots \left\lfloor\sqrt{p}\right\rfloor$. There are a total of $\left(\left\lfloor\sqrt{p}\right\rfloor+1\right)^2>p$ choices of $x$ and $y$.

But for each of them, there are $p$ possible values of $y-x\alpha$ in (mod $p$). So by the Pigeonhole Principle, there must be some $0\leq x_1,x_2,y_1,y_2\leq \left\lfloor\sqrt{p}\right\rfloor$ such that

\begin{align*} y_1-x_1\alpha &\equiv y_2-x_2\alpha\pmod{p}\\ \implies y_1-y_2 &\equiv\alpha(x_1-x_2)\pmod{p}\\ \implies (y_1-y_2)^2 &\equiv\alpha^2(x_1-x_2)^2\pmod{p}\\ &\equiv-(x_1-x_2)^2\pmod{p}. \end{align*}

Now, let $a=|x_1-x_2|$ and $a=|y_1-y_2|$. We know that $p\mid a^2+b^2$, and $0\leq a,b\leq \left\lfloor\sqrt{p}\right\rfloor<\sqrt{p}$. So $0<a^2+b^2<2(\sqrt{p})^2=2p$. Clearly $a^2+b^2=p$ as required.

Having shown correspondence both sides, we have established the result.