Which Numbers are the Sum of Two Squares?

eimhee

浏览: 2110238 次
性别:
来自: 北京

最近访客更多访客>>

loginboot

u012363178

feichuanliushi

xx5333

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

The main goal of today's lecture is to prove the following theorem.

Theorem 1.1 A number

is a sum of two squares if and only if all prime factors of

of the form

have even exponent in the prime factorization of

Before tackling a proof, we consider a few examples.

Example 1.2

.
is not a sum of two squares.
is divisible by because is, but not by since is not, so is not a sum of two squares.
$2\cdot 3^4\cdot 5\cdot 7^2\cdot 13$ is a sum of two squares.
is a sum of two squares, since  $389\equiv 1\pmod{4}$ and is prime.
$21=3\cdot 7$ is not a sum of two squares even though  $21\equiv 1\pmod{4}$ .

In preparation for the proof of Theorem 1.1, we recall a result that emerged when we analyzed how partial convergents of a continued fraction converge.

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

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

Proof. Let  $[a_0,a_1,\ldots]$ be the continued fraction expansion of

. As we saw in the proof of Theorem 2.3 in Lecture 18, for each

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

Since $q_{m+1}$ is always at least bigger than and , either there exists an such that  $q_m\leq n < q_{m+1}$ , or the continued fraction expansion of is finite and is larger than the denominator of the rational number . In the first case,

$\displaystyle \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  $\displaystyle \frac{a}{b} = \frac{p_m}{q_m}$ satisfies the conclusion of the lemma. In the second case, just let  $\displaystyle \frac{a}{b} = x$ .

$\qedsymbol$

Definition 1.4 A representation

is primitive if  $\gcd(x,y)=1$ .

Lemma 1.5 If

is divisible by a prime

of the form

, then

has no primitive representations.

Proof. If

has a primitive representation,

, then

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

so $p\nmid x$ and $p\nmid y$ . Thus  $x^2 + y^2 \equiv 0\pmod{p}$ so, since  $\mathbb{Z}/p\mathbb{Z}$ is a field we can divide by and see that

$\displaystyle (x/y)^2 \equiv -1\pmod{p}.$

Thus the quadratic residue symbol  $\left(\frac{-1}{p}\right)$ equals . However,

$\displaystyle \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = (-1)^\frac{4m+3-1}{2} = (-1)^{2m+1} = -1.$

$\qedsymbol$

Proof. [Proof of Theorem 1.1]  $\left(\Longrightarrow\right)$ Suppose that

is of the form

, that  $p^r\mid\mid n$ (exactly divides) with

odd, and that

. Letting  $d=\gcd(x,y)$ , we have

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

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

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

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

$\left(\Longleftarrow\right)$ Write  where has no prime factors of the form . It suffices to show that is a sum of two squares. Also note that

$\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,$

so a product of two numbers that are sums of two squares is also a sum of two squares.¹Also, the prime is a sum of two squares. It thus suffices to show that if is a prime of the form , then is a sum of two squares.

Since

$\displaystyle (-1)^{\frac{p-1}{2}} = (-1)^{\frac{4m+1-1}{2}} = +1,$

is a square modulo ; i.e., there exists such that  $r^2\equiv -1\pmod{p}$ . Taking  $n=\lfloor \sqrt{p}\rfloor$ in Lemma 1.3 we see that there are integers such that  $0<b<\sqrt{p}$ and