Sums of Two Squares

In this section we apply continued fractions to prove the following theorem.

Theorem 5.6   A positive integer $n$ is a sum of two squares if and only if all prime factors of $p\mid n$ such that $p\equiv 3 \pmod{4}$ have even exponent in the prime factorization of $n$ .

We first consider some examples. Notice that $5 = 1^2 + 2^2$ is a sum of two squares, but $7$ is not a sum of two squares. Since $2001$ is divisible by $3$ (because $2+1$ is divisible by $3$ ), but not by $9$ (since $2+1$ is not), Theorem 5.6.1 implies that $2001$ is not a sum of two squares. The theorem also implies that $2\cdot 3^4\cdot 5\cdot 7^2\cdot 13$ is a sum of two squares.

SAGE Example 5.6   We use SAGE to write a short program that naively determines whether or not an integer $n$ is a sum of two squares, and if so returns $a, b$ such that $a^2 + b^2 = n$ .

sage: def sum_of_two_squares_naive(n):
...    for i in range(int(sqrt(n))):
...        if is_square(n - i^2): 
...            return i, (Integer(n-i^2)).sqrt()
...    return "%s is not a sum of two squares"%n

We next use our function in a couple of cases.

sage: sum_of_two_squares_naive(23) 
'23 is not a sum of two squares'
sage: sum_of_two_squares_naive(389)
(10, 17)
sage: sum_of_two_squares_naive(2007) 
'2007 is not a sum of two squares'
sage: sum_of_two_squares_naive(2008)  
'2008 is not a sum of two squares'
sage: sum_of_two_squares_naive(2009)   
(28, 35)
sage: 28^2 + 35^2
2009
sage: sum_of_two_squares_naive(2*3^4*5*7^2*13)
(189, 693)

Definition 5.6 (Primitive)   A representation $n=x^2 + y^2$ is primitive if $x$ and $y$ are coprime.

Lemma 5.6   If $n$ is divisible by a prime  $p\equiv 3 \pmod{4}$ , then $n$ has no primitive representations.

Proof. Suppose $n$ has a primitive representation, $n=x^2 + y^2$ , and let $p$ be any prime factor of $n$ . Then

$$p \mid x^2 + y^2$$    and $$\quad \gcd(x,y)=1,$$

so $p\nmid x$ and $p\nmid y$ . Since $\mathbb{Z}/p\mathbb{Z}{}$ is a field we may divide by $y^2$ in the equation $x^2 + y^2 \equiv 0\pmod{p}$ to see that $(x/y)^2 \equiv -1\pmod{p}.$ Thus the Legendre symbol $\left(\frac{-1}{p}\right)$ equals $+1$ . However, by Proposition 4.2.1,

$$\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$$

so $\left(\frac{-1}{p}\right)=1$ if and only if $(p-1)/2$ is even, which is to say $p\equiv 1\pmod{4}$ . $\qedsymbol$

Proof. [Proof of Theorem 5.6.1 $\left(\Longrightarrow\right)$ ] Suppose that $p\equiv 3 \pmod{4}$ is a prime, that $p^r\mid n$ but $p^{r+1}\nmid n$ with $r$ odd, and that $n=x^2 + y^2$ . Letting $d=\gcd(x,y)$ , we have

$$x = dx', \quad y = dy',$$    and $$\quad n = d^2 n'$$

with $\gcd(x',y')=1$ and

$$(x')^2 + (y')^2 = n'.$$

Because $r$ is odd, $p\mid n'$ , so Lemma 5.6.4 implies that $\gcd(x',y')>1$ , a contradiction. $\qedsymbol$

To prepare for our proof of $\left(\Longleftarrow\right)$ , we reduce the problem to the case when $n$ is prime. Write $n=n_1^2 n_2$ where $n_2$ has no prime factors $p\equiv 3 \pmod{4}$ . It suffices to show that $n_2$ is a sum of two squares, since

$$(x_1^2 + y_1^2)(x_2^2+y_2^2) = (x_1x_2-y_1y_2)^2 + (x_1y_2+x_2y_1)^2,$$ (5.6.1)

so a product of two numbers that are sums of two squares is also a sum of two squares. Since $2=1^2+1^2$ is a sum of two squares, it suffices to show that any prime $p\equiv 1\pmod{4}$ is a sum of two squares.

Lemma 5.6   If $x\in\mathbb{R}$ and $n\in\mathbb{N}$ , then there is a fraction $$\frac{a}{b}$$ in lowest terms such that $0<b\leq n$ and

$$\left\vert x - \frac{a}{b} \right\vert \leq \frac{1}{b(n+1)}.$$

Proof. Consider the continued fraction $[a_0, a_1, \ldots]$ of $x$ . By Corollary 5.2.11, for each $m$

$$\left\vert x - \frac{p_m}{q_m}\right\vert < \frac{1}{q_m \cdot q_{m+1}}.$$

Since $q_{m+1}\geq q_m + 1$ and $q_0=1$ , either there exists an $m$ such that $q_m\leq n < q_{m+1}$ , or the continued fraction expansion of $x$ is finite and $n$ is larger than the denominator of the rational number $x$ , in which case we take $\frac{a}{b}=x$ and are done. In the first case,

$$\left\vert x - \frac{p_m}{q_m}\right\vert < \frac{1}{q_m \cdot q_{m+1}} \leq \frac{1}{q_m \cdot (n+1)},$$

so $$\frac{a}{b} = \frac{p_m}{q_m}$$ satisfies the conclusion of the lemma. $\qedsymbol$

Proof. [Proof of Theorem 5.6.1 $\left(\Longleftarrow\right)$ ] As discussed above, it suffices to prove that any prime $p\equiv 1\pmod{4}$ is a sum of two squares. Since $p\equiv 1\pmod{4}$ ,

$$(-1)^{(p-1)/2} = 1,$$

so Proposition 4.2.1 implies that $-1$ is a square modulo $p$ ; i.e., there exists  $r\in\mathbb{Z}$ such that $r^2\equiv -1\pmod{p}$ . Lemma 5.6.5, with $n=\lfloor \sqrt{p}\rfloor$ and $x=-\frac{r}{p}$ , implies that there are integers $a, b$ such that $0<b<\sqrt{p}$ and

$$\left\vert -\frac{r}{p} - \frac{a}{b}\right\vert \leq\frac{1}{b(n+1)} < \frac{1}{b\sqrt{p}}.$$

Letting $c = rb + pa$ , we have that

$$\vert c\vert < \frac{pb}{b\sqrt{p}} = \frac{p}{\sqrt{p}} = \sqrt{p}$$

so

$$0 < b^2 + c^2 < 2p.$$

But $c \equiv rb\pmod{p}$ , so

$$b^2 + c^2 \equiv b^2 + r^2 b^2 \equiv b^2(1+r^2) \equiv 0\pmod{p}.$$

Thus $b^2 + c^2 = p$ . $\qedsymbol$

Remark 5.6   Our proof of Theorem 5.6.1 leads to an efficient algorithm to compute a representation of any $p\equiv 1\pmod{4}$ as a sum of two squares.

SAGE Example 5.6   We next use SAGE and Theorem 5.6.1 to give an efficient algorithm for writing a prime $p\equiv 1\pmod{4}$ as a sum of two squares. First we implement the algorithm that comes out of the proof of the theorem.

sage: def sum_of_two_squares(p):
...    p = Integer(p)
...    assert p%4 == 1, "p must be 1 modulo 4"
...    r = Mod(-1,p).sqrt().lift()
...    v = continued_fraction(-r/p)         
...    n = floor(sqrt(p))
...    for x in v.convergents():                       
...        c = r*x.denominator() + p*x.numerator()                                
...        if -n <= c and c <= n: 
...            return (abs(x.denominator()),abs(c))

Next we use the algorithm to write the first $10$ -digit prime $\equiv 1\pmod{4}$ as a sum of two squares:

sage: p = next_prime(next_prime(10^10)) 
sage: sum_of_two_squares(p)
(55913, 82908)

The above calculation was essentially instantanoues. If instead we use the naive algorithm from before, it takes several seconds to write $p$ as a sum of two squares.

sage: sum_of_two_squares_naive(p)
(55913, 82908)