Exercise 7.3.6 (Hermite's method for Fermat's theorem on sums of two squares)

Proof. We suppose that $p\equiv 1(\mathit{mod}4)$. Then $\left(\frac{-1}{p}\right)={(-1)}^{(p-1)∕2}=1$, so there exists some integer $u$ such that $u^2\equiv -1(\mathit{mod}p)$.

Write $u∕p=⟨a_0,a_1,\dots ,a_n⟩$. Since $k_0=1\le \sqrt{p}$, there exists a largest integer $i\in [[0,n]]$ such that $k_i\le \sqrt{p}$. Since the sequence ${(k_i)}_{0\le i\le n}$ is increasing, this means that

By Problem 5,

• If $i=n$,

  $$\begin{array}{llll}\hfill \left|\frac{h_i}{k_i}-\frac{u}{p}\right|& =\left|\frac{h_n}{k_n}-\frac{u}{p}\right|=0<\frac{1}{k_i\sqrt{p}}.& \hfill & \end{array}$$

• If $0\le i\le n-1$, then

  $$\begin{array}{lllllll}\hfill \left|\frac{h_i}{k_i}-\frac{u}{p}\right|& \le \frac{1}{k_i{k}_{i+1}}& \hfill (\text{by (2)})& & \hfill & & \hfill \\ \hfill & <\frac{1}{k_i\sqrt{p}}& \hfill (\text{by (1)}).& & \hfill & & \hfill \end{array}$$

In either case,

hence

Put $x=k_i,y=h_{i}p-u{k}_i$. Then $x=k_i\ge k_1=1$, thus $x^2+y^2>0$, and by (1) and (3),

So

Moreover

since $u^2+1\equiv 0(\mathit{mod}p)$.

The only multiple $m$ of $p$ such that $0<m<2p$ is $p$, so

This gives another proof of Fermat’s theorem on sums of two squares, and one more fast algorithm to find $x,y$ such that $x^2+y^2=p$ (if $p\equiv 1(\mathit{mod}4)$). □