Which Numbers are the Sum of Two Squares?

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  

  • $ 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.
  • $ 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 $ 389/equiv 1/pmod{4}$ and $ 389$ 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 $ x$. As we saw in the proof of Theorem 2.3 in Lecture 18, for each $ m$

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

$/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 $ n=x^2 + y^2$ is primitive if $ /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, $ n=x^2 + y^2$, 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 $ y^2$ and see that

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

Thus the quadratic residue symbol $ /left(/frac{-1}{p}/right)$ equals $ +1$. 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 $ p$ is of the form $ 4m+3$, that $ p^r/mid/mid n$ (exactly divides) with $ r$ odd, and that $ n=x^2 + y^2$. 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 $ r$ is odd, $ p/mid n'$, so Lemma 1.5 implies that $ /gcd(x',y')>1$, a contradiction.

$ /left(/Longleftarrow/right)$ Write $ 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

$/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

$/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 $ r^2/equiv -1/pmod{p}$. Taking $ n=/lfloor /sqrt{p}/rfloor$ in Lemma 1.3 we see that there are integers $ a, b$ such that $ 0<b</sqrt{p}$ and

$/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

$/displaystyle c = rb + pa $

then

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

and

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

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

$/displaystyle 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$.
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/fengju/p/6336252.html