Expressing Prime Numbers as Sums of Two Squares

Theorem (Expressing Prime Numbers as Sums of Two Squares)
A prime  
\[p\]
  can be expressed as a sum of two squares if and only if  
\[p \equiv 2 \; (mod \; 4)\]
  or  
\[p \equiv 1 \; (mod \; 4)\]
.
Proof>br /> Suppose the equation  
\[mp=x^2+y^2\]
  such that  
\[1 \lt m \lt p\]
. Let  
\[u, \; v\]
  be the least absolute residue modulo  
\[m\]
  of  
\[x, \; y\]
  respectively. Then
\[u \equiv x \; (mod \; m), \; v \equiv y \; (mod \; m), \; - \frac{m}{2} \lt u, \; v \lt \frac{m}{2}\]
  and  
\[u^2+v^2=x^2+y^2 \; (mod \; m)\]
.
\[u, \; v\]
  must satisfy  
\[u^2+v^2=mr\]

If  
\[r=0\]
  then  
\[u=v=0\]
  so  
\[m\]
  divides both  
\[x\]
  and  
\[y\]
  so  
\[m\]
  divides  
\[p\]
  (using  
\[mp=x^2+y^2\]
), which is impossible.
\[1 \lt r= \frac{u^2+v^2}{m} \lt \frac{1}{m} \times (\frac{m^2+m^2}{4}) = \frac{m}{2} \lt m\]

Multiply  
\[mp=x^2+y^2\]
  by  
\[mr=u^2+v^2\]
  and write as a sum of squares.
\[(mp)(mr)=(x^2+y^2)(u^2+v^2)=(xu+yv)^2+(xv-yu)^2 \]
 
Now  
\[xu+yv \equiv x^2+y^2 \equiv 0 \; (mod \; m) \rightarrow m | (xu+yv)\]

Now  
\[xv-yu \equiv xy-xy \equiv 0 \; (mod \; m) \rightarrow m | (xv-yu)\]

Put  
\[xu+yv=mX, \; xv-yu=mY\]
  and substitute into (1), obtaining  
\[m^2rp=m^2X^2+m^2Y^2 \rightarrow rp=X^2+Y^2\]
.
Repeating if necessary we reach  
\[m=1\]
  eventually.
-1 is a Quadratic Residue of  
\[p\]
  if  
\[p \equiv 1 \; (mod \; 4)\]
. The congruence  
\[x^2 \equiv -1 \; (mod \; p)\]
  has a least positive solution  
\[0 \lt x_1 \le p-1\]
  so there exists  
\[m \gt 0\]
  such that  
\[mp=x_1^1_1^2\]
  which is exactly what is required since
\[m=\frac{x^2+1+1^2}{p} \lt \frac{(p-1)^2+1}{p}=\frac{p^2-2(p-1)}{p}{p} \lt p\]
>br /> If this solution has  
\[m \gt 1\]
  we cancel down to 1 as above and find a solution.

Add comment

Security code
Refresh