Fermat's Two Squares Theorem

From ProofWiki
Jump to: navigation, search


Theorem

Let $p$ be a prime number.


Then $p$ can be expressed as the sum of two squares if and only if either:

$p = 2$

or:

$p \equiv 1 \pmod 4$


The expression of a prime of the form $4 k + 1$ as the sum of two squares is unique except for the order of the two summands.


Proof

Proof of Existence

There are three possibilities for a prime:

$(1): \quad p = 2$

or:

$(2): \quad p \equiv 1 \pmod 4$

or:

$(3): \quad p \equiv 3 \pmod 4$


Necessary Condition

Suppose $p$ can be expressed as the sum of two squares.

First we note that $2 = 1^2 + 1^2$, which is the sum of two squares.

This disposes of the case where $p = 2$.


Let $p = a^2 + b^2$.

From Sum of Two Squares not Congruent to 3 modulo 4, $p \not \equiv 3 \pmod 4$ whatever $a$ and $b$ are.

So either $p = 2$, or $p \equiv 1 \pmod 4$.


Sufficient Condition

We have already noted that $2 = 1^2 + 1^2$, which is the sum of two squares.

Let $p$ be a prime number of the form $p \equiv 1 \pmod 4$.

Suppose $m p = x^2 + y^2$ has a solution such that $1 < m < p$.

Let $u, v$ be the least absolute residues modulo $m$ of $x$ and $y$ respectively.

That is:

$u \equiv x, v \equiv y \pmod m: \dfrac {-m} 2 < u, v \le \dfrac m 2$

Then:

$u^2 + v^2 \equiv x^2 + y^2 \pmod m$

Thus:

$\exists r \in \Z, r \ge 0: u^2 + v^2 = m r$


We are going to establish a descent step.

That is, we aim to show that $r p$ is the sum of two squares with $1 \le r < m$.

First we show that $r$ does lie in this range.

If $r = 0$ then $u = v = 0$ and so $m$ divides both $x$ and $y$.

But then from $m p = x^2 + y^2$ we have that $m \mathrel \backslash p$.

This cannot happen as $p$ is prime.

So:

$1 \le r = \dfrac {u^2 + v^2} m \le \dfrac 1 m \times \left({\dfrac {m^2} 4 + \dfrac {n^2} 4}\right) = \dfrac m 2 < m$

So $1 \le r < m$.


Now we show that $r p$ is the sum of two squares.

Multiplying $m p = x^2 + y^2$ and $m r = u^2 + v^2$:

\(\displaystyle m^2 r p\) \(=\) \(\displaystyle \left({x^2 + y^2}\right) \left({u^2 + v^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({x u + y v}\right)^2 + \left({x v - y u}\right)^2\) $\quad$ Brahmagupta-Fibonacci Identity $\quad$

Now:

$x u + y v \equiv x^2 + y^2 \equiv 0 \pmod m$, so $m \mathrel \backslash x u + y v$
$x v - y u \equiv x y - x y \equiv 0 \pmod m$, so $m \mathrel \backslash x v - y u$

So, putting $m X = x u + y v, m Y = x v - y u$, we get:

$m^2 r p = m^2 X^2 + m^2 Y^2$

That is:

$r p = X^2 + Y^2$

Hence the descent step is established.


Next we need to show that $m p = x^2 + y^2$ has a solution for some $m$ with $1 \le m < p$.

From First Supplement to Law of Quadratic Reciprocity, we have that $-1$ is a quadratic residue for each prime $p \equiv 1 \pmod 4$.

Hence the congruence $x^2 + 1 \equiv 0 \pmod p$ has a least positive solution $x_1$ such that $1 \le x_1 \le p - 1$.

So there exists a positive integer $m$ such that $m p = x_1^2 + 1^2$.

This is just what we want, because:

$m = \dfrac {x_1^2 + 1^2} p \le \dfrac {\left({p - 1}\right)^2 + 1} p = \dfrac {p^2 - 2 \left({p - 1}\right)^2} p < p$

If this solution has $m > 1$, then our descent step (above) guarantees a solution for a smaller positive value of $m$.

Eventually we will reach a solution with $m = 1$, that is:

$p = x^2 + y^2$

$\blacksquare$


Proof of Uniqueness

Let $p$ be prime such that $p \equiv 1 \pmod 4$.

Suppose $p = a^2 + b^2 = c^2 + d^2$ where $a > b > 0$ and $c > d > 0$.

We are going to show that $a = c$ and $b = d$.

From the two expressions for $p$, we have:

\(\displaystyle \left({a d - b c}\right) \left({a d + b c}\right)\) \(=\) \(\displaystyle a^2 d^2 - b^2 c^2\) $\quad$ Difference of Two Squares $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({p - b^2}\right) d^2 - b^2 \left({p - d^2}\right)\) $\quad$ substituting for $a^2$ and $c^2$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle p d^2 - b^2 d^2 - p b^2 + b^2 d^2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle p \left({d^2 - b^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\equiv\) \(\displaystyle 0\) $\quad$ $\pmod p$ $\quad$

So we have:

$\left({a d - b c}\right) \left({a d + b c}\right) \equiv 0 \pmod p$

From Euclid's Lemma, that means:

$p \mathrel \backslash \left({a d - b c}\right)$

or:

$p \mathrel \backslash \left({a d + b c}\right)$


So, suppose $p \mathrel \backslash \left({a d + b c}\right)$.

Now, we have that each of $a^2, b^2, c^2, d^2$ must be less than $p$.

Hence $0 < a, b, c, d < \sqrt p$.

This implies $0 < a d + b c < 2p$.

That must mean that $a d + b c = p$.

But then:

\(\displaystyle p^2\) \(=\) \(\displaystyle \left({a^2 + b^2}\right) \left({d^2 + c^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({a d + b c}\right)^2 + \left({a c - b d}\right)^2\) $\quad$ Brahmagupta-Fibonacci Identity $\quad$
\(\displaystyle \) \(=\) \(\displaystyle p^2 + \left({a c - b d}\right)^2\) $\quad$ $\quad$

That means:

$a c - b d = 0$

But since $a > b$ and $c > d$ we have:

$a c > b d$

This contradiction shows that $a d + b c$ can not be divisible by $p$.


So this means:

$p \mathrel \backslash \left({a d - b c}\right)$

Similarly, because $0 < a, b, c, d < \sqrt p$ we have:

$-p < a d - b c < p$

This means:

$a d = b c$

So:

$a \mathrel \backslash b c$

But $a \perp b$ otherwise $a^2 + b^2$ has a common divisor greater than $1$ and less than $p$.

This cannot happen because $p$ is prime.

So by Euclid's Lemma:

$a \mathrel \backslash c$

So we can put $c = k a$ and so $a d = b c$ becomes $d = k b$.

Hence:

$p = c^2 + d^2 = k^2 \left({a^2 + b^2}\right) = k^2 p$

This means $k = 1$ which means $a = c$ and $b = d$ as we wanted to show.

$\blacksquare$


Also known as

It is also known as just the Two Squares Theorem.


Also see


Source of Name

This entry was named for Pierre de Fermat.


Sources