Sums of Two Squares
In this section we apply continued fractions to prove
the following theorem.
Theorem 5.6
A positive integer
is a sum of two squares if and only if all
prime factors of
such that
have even
exponent in the prime factorization of
.
We first consider some examples. Notice that
is a sum
of two squares, but
is not a sum of two squares. Since
is
divisible by
(because
is divisible by
),
but not by
(since
is not),
Theorem 5.6.1 implies that
is not a sum of two
squares. The theorem also implies that
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$](img7.png)
is a sum of two squares, and if
so returns
![$ a, b$](img136.png)
such that
![$ a^2 + b^2 = n$](img1973.png)
.
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$](img1974.png)
is
primitive
if
![$ x$](img227.png)
and
![$ y$](img364.png)
are coprime.
Lemma 5.6
If
is divisible by a prime
, then
has no primitive representations.
Proof.
Suppose
![$ n$](img7.png)
has a primitive representation,
![$ n=x^2 + y^2$](img1974.png)
, and
let
![$ p$](img14.png)
be any prime factor of
![$ n$](img7.png)
. Then
![$\displaystyle p \mid x^2 + y^2$](img1975.png)
and
so
![$ p\nmid x$](img1977.png)
and
![$ p\nmid y$](img1978.png)
.
Since
![$ \mathbb{Z}/p\mathbb{Z}{}$](img424.png)
is a field we may divide by
![$ y^2$](img1979.png)
in the equation
![$ x^2 + y^2 \equiv 0\pmod{p}$](img1980.png)
to see that
![$ (x/y)^2 \equiv -1\pmod{p}.
$](img1981.png)
Thus the Legendre symbol
![$ \left(\frac{-1}{p}\right)$](img1982.png)
equals
![$ +1$](img1253.png)
.
However, by Proposition
4.2.1,
so
![$ \left(\frac{-1}{p}\right)=1$](img1983.png)
if and only if
![$ (p-1)/2$](img992.png)
is even, which is
to say
![$ p\equiv 1\pmod{4}$](img1454.png)
.
Proof.
[Proof of Theorem
5.6.1
![$ \left(\Longrightarrow\right)$](img1984.png)
]
Suppose that
![$ p\equiv 3 \pmod{4}$](img1451.png)
is a prime, that
![$ p^r\mid n$](img1985.png)
but
![$ p^{r+1}\nmid n$](img1986.png)
with
![$ r$](img97.png)
odd, and that
![$ n=x^2 + y^2$](img1974.png)
. Letting
![$ d=\gcd(x,y)$](img1987.png)
, we have
![$\displaystyle x = dx', \quad y = dy',$](img1988.png)
and
with
![$ \gcd(x',y')=1$](img1990.png)
and
Because
![$ r$](img97.png)
is odd,
![$ p\mid n'$](img1992.png)
, so Lemma
5.6.4
implies that
![$ \gcd(x',y')>1$](img1993.png)
, a contradiction.
To prepare for our proof of
, we reduce
the problem to the case when
is prime. Write
where
has no prime factors
. It suffices to show
that
is a sum of two squares, since
![$\displaystyle (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,$](img1997.png) |
(5.6.1) |
so a product of two numbers that are sums of two squares is also
a sum of two squares.
Since
is a sum of two squares, it suffices to show
that any prime
is a sum of two squares.
Proof.
Consider the continued fraction
![$ [a_0, a_1, \ldots]$](img1897.png)
of
![$ x$](img227.png)
.
By Corollary
5.2.11, for each
Since
![$ q_{m+1}\geq q_m + 1$](img2002.png)
and
![$ q_0=1$](img2003.png)
,
either there exists an
![$ m$](img266.png)
such that
![$ q_m\leq n < q_{m+1}$](img2004.png)
, or the
continued fraction
expansion of
![$ x$](img227.png)
is finite and
![$ n$](img7.png)
is larger
than the denominator of the rational number
![$ x$](img227.png)
, in which case
we take
![$ \frac{a}{b}=x$](img2005.png)
and are done. In the first
case,
so
![$ \displaystyle \frac{a}{b} = \frac{p_m}{q_m}$](img2007.png)
satisfies the conclusion of
the lemma.
Proof.
[Proof of Theorem
5.6.1
![$ \left(\Longleftarrow\right)$](img1994.png)
]
As discussed above, it suffices to prove that any prime
![$ p\equiv 1\pmod{4}$](img1454.png)
is a sum of two squares. Since
![$ p\equiv 1\pmod{4}$](img1454.png)
,
so Proposition
4.2.1 implies that
![$ -1$](img53.png)
is a square modulo
![$ p$](img14.png)
; i.e., there exists
![$ r\in\mathbb{Z}$](img2009.png)
such
that
![$ r^2\equiv -1\pmod{p}$](img2010.png)
.
Lemma
5.6.5, with
![$ n=\lfloor \sqrt{p}\rfloor$](img2011.png)
and
![$ x=-\frac{r}{p}$](img2012.png)
,
implies that there are integers
![$ a, b$](img136.png)
such that
![$ 0<b<\sqrt{p}$](img2013.png)
and
Letting
![$ c = rb + pa$](img2015.png)
, we have that
so
But
![$ c \equiv rb\pmod{p}$](img2018.png)
, so
Thus
![$ b^2 + c^2 = p$](img2020.png)
.
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}$](img1454.png)
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}$](img1454.png)
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$](img1951.png)
-digit
prime
![$ \equiv 1\pmod{4}$](img2021.png)
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$](img14.png)
as a sum of two squares.
sage: sum_of_two_squares_naive(p)
(55913, 82908)
William
2007-06-01