`
ihuashao
  • 浏览: 4533810 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

Which Numbers are the Sum of Two Squares?

CC++C# 
阅读更多
The main goal of today's lecture is to prove the following theorem.

Theorem 1.1 A number$ n$ is a sum of two squares if and only if all prime factors of$ n$ of the form $ 4m+3$ have even exponent in the prime factorization of$ n$.

Before tackling a proof, we consider a few examples.

Example 1.2

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

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

Lemma 1.3 If <!-- MATH $x\in\mathbb{R}$ -->$ x\in\mathbb{R}$ and <!-- MATH $n\in\mathbb{N}$ -->$ n\in\mathbb{N}$, then there is a fraction <!-- MATH $\displaystyle \frac{a}{b}$ -->$ \displaystyle \frac{a}{b}$ in lowest terms such that $ 0<b\leq n$ and <!-- MATH \begin{displaymath} \left| x - \frac{a}{b} \right| \leq \frac{1}{b(n+1)}. \end{displaymath} -->

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

Proof. Let <!-- MATH $[a_0,a_1,\ldots]$ -->$ [a_0,a_1,\ldots]$ be the continued fraction expansion of$ x$. As we saw in the proof of Theorem2.3 in Lecture18, for each$ m$<!-- MATH \begin{displaymath} \left| x - \frac{p_m}{q_m}\right| < \frac{1}{q_m \cdot q_{m+1}}. \end{displaymath} -->

$\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$ 1$ bigger than $ q_m$ and $ q_0=1$, either there exists an$ m$ such that <!-- MATH $q_m\leq n < q_{m+1}$ -->$ 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 the first case, <!-- MATH \begin{displaymath} \left| x - \frac{p_m}{q_m}\right| < \frac{1}{q_m \cdot q_{m+1}} \leq \frac{1}{q_m \cdot (n+1)}, \end{displaymath} -->

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

$ \qedsymbol$

Definition 1.4 A representation <!-- MATH $n=x^2 + y^2$ -->$ n=x^2 + y^2$ is primitive if <!-- MATH $\gcd(x,y)=1$ -->$ \gcd(x,y)=1$.

Lemma 1.5 If$ n$ is divisible by a prime$ p$ of the form $ 4m+3$, then$ n$ has no primitive representations.

Proof. If$ n$ has a primitive representation, <!-- MATH $n=x^2 + y^2$ -->$ n=x^2 + y^2$, then <!-- MATH \begin{displaymath} p \mid x^2 + y^2\quad \text{ and }\quad \gcd(x,y)=1, \end{displaymath} -->

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

so $ p\nmid x$ and $ p\nmid y$. Thus <!-- MATH $x^2 + y^2 \equiv 0\pmod{p}$ -->$ x^2 + y^2 \equiv 0\pmod{p}$ so, since <!-- MATH $\mathbb{Z}/p\mathbb{Z}$ -->$ \mathbb{Z}/p\mathbb{Z}$ is a field we can divide by $ y^2$ and see that <!-- MATH \begin{displaymath} (x/y)^2 \equiv -1\pmod{p}. \end{displaymath} -->

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

Thus the quadratic residue symbol <!-- MATH $\left(\frac{-1}{p}\right)$ -->$ \left(\frac{-1}{p}\right)$ equals $ +1$. However, <!-- MATH \begin{displaymath} \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = (-1)^\frac{4m+3-1}{2} = (-1)^{2m+1} = -1. \end{displaymath} -->

$\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 Theorem1.1] <!-- MATH $\left(\Longrightarrow\right)$ -->$ \left(\Longrightarrow\right)$ Suppose that$ p$ is of the form $ 4m+3$, that <!-- MATH $p^r\mid\mid n$ -->$ p^r\mid\mid n$ (exactly divides) with$ r$ odd, and that $ n=x^2 + y^2$. Letting <!-- MATH $d=\gcd(x,y)$ -->$ d=\gcd(x,y)$, we have <!-- MATH \begin{displaymath} x = dx', \quad y = dy', \quad n = d^2 n' \end{displaymath} -->

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

with <!-- MATH $\gcd(x',y')=1$ -->$ \gcd(x',y')=1$ and <!-- MATH \begin{displaymath} (x')^2 + (y')^2 = n'. \end{displaymath} -->

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

Because$ r$ is odd, $ p\mid n'$, so Lemma1.5 implies that <!-- MATH $\gcd(x',y')>1$ -->$ \gcd(x',y')>1$, a contradiction.

<!-- MATH $\left(\Longleftarrow\right)$ -->$ \left(\Longleftarrow\right)$ Write <!-- MATH $n=n_1^2 n_2$ -->$ n=n_1^2 n_2$ where $ n_2$ has no prime factors of the form $ 4m+3$. It suffices to show that$ n_2$ is a sum of two squares. Also note that <!-- MATH \begin{displaymath} (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, \end{displaymath} -->

$\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.1Also, the prime$ 2$ is a sum of two squares. It thus suffices to show that if$ p$ is a prime of the form $ 4m+1$, then$ p$ is a sum of two squares.

Since <!-- MATH \begin{displaymath} (-1)^{\frac{p-1}{2}} = (-1)^{\frac{4m+1-1}{2}} = +1, \end{displaymath} -->

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

$ -1$ is a square modulo$ p$; i.e., there exists$ r$ such that <!-- MATH $r^2\equiv -1\pmod{p}$ -->$ r^2\equiv -1\pmod{p}$. Taking <!-- MATH $n=\lfloor \sqrt{p}\rfloor$ -->$ n=\lfloor \sqrt{p}\rfloor$ in Lemma1.3 we see that there are integers $ a, b$ such that <!-- MATH $0<b<\sqrt{p}$ -->$ 0<b<\sqrt{p}$ and <!-- MATH \begin{displaymath} \left| -\frac{r}{p} - \frac{a}{b}\right| \leq\frac{1}{b(n+1)} < \frac{1}{b\sqrt{p}}. \end{displaymath} -->

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

If we write <!-- MATH \begin{displaymath} c = rb + pa \end{displaymath} -->

$\displaystyle c = rb + pa $

then <!-- MATH \begin{displaymath} |c| < \frac{pb}{b\sqrt{p}} = \frac{p}{\sqrt{p}} = \sqrt{p} \end{displaymath} -->

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

and <!-- MATH \begin{displaymath} 0 < b^2 + c^2 < 2p. \end{displaymath} -->

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

But <!-- MATH $c \equiv rb\pmod{p}$ -->$ c \equiv rb\pmod{p}$, so <!-- MATH \begin{displaymath} b^2 + c^2 \equiv b^2 + r^2 b^2 \equiv b^2(1+r^2) \equiv 0\pmod{p}. \end{displaymath} -->

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

Thus <!-- MATH $b^2 + c^2 = p$ -->$ b^2 + c^2 = p$.
分享到：
| 咏春拳
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics