Sums of Squares – Continued Fractions – A Neighbourhood Of Infinity

Given a prime $\displaystyle p \equiv 1 \mod 4 ,$ we want to find solutions to $\displaystyle p =x^2+y^2.$

Method 1: Find the solution ${t}$ of ${t^{2} \equiv-1(\bmod ~p),}$ where ${0<t<p / 2.}$
Expand ${t/ p}$ into a simple continued fraction to the point where the denominators of its convergents ${p_{n} / q_{n}}$ satisfy the inequality ${q_{k}<\sqrt{p}<q_{k+1} .}$ Then

$\displaystyle p=\left(t q_{k}-p p_{k}\right)^{2}+\left(q_{k}\right)^{2}$

Proof: For any ${m}$ , we have
$\displaystyle \left|\frac{t}{p}-\frac{p_{m}}{q_{m}}\right|<\frac{1}{q_{m+1} \cdot q_{m}}$
which is true for any continued fraction expansion.

Let $\displaystyle x=t\cdot q_{m}-p \cdot p_{m}$
$\displaystyle \left|\frac{x}{p \cdot q_{m}}\right|=\left|\frac{t}{p}-\frac{p_{m}}{q_{m}}\right|<\frac{1}{q_{m+1} \cdot q_{m}}$

Take $\displaystyle ~~m=k$

$\displaystyle |x|<\frac{p}{\sqrt{p}}=\sqrt{p}$
$\displaystyle x^{2}+q_{m}^{2}<p+p=2 p$

We have
$\displaystyle x \equiv tq_m \bmod ~p$
$\displaystyle x^2+q_m^2 \equiv 0 \bmod ~p$

Therefore
$\displaystyle x^{2}+q_{m}^{2}=p$

Method 2:

$\displaystyle \frac{p}{t}=\left[a_{0} ; a_{1}, \ldots, a_{m}, a_{m}, \ldots, a_{1}, a_{0}\right]$

$\displaystyle \frac{p_{m-1} }{ q_{m-1}} =\left[a_{0} ; a_{1}, \ldots, a_{m-1}\right],$

$\displaystyle \frac{p_{m} }{ q_{m}} =\left[a_{0} ; a_{1}, \ldots, a_{m-1}, a_m\right].$

Then :
If ${p_1>1 }$ then ${x=p_{m-1}, y=p_{m}}$ satisfy ${x^2+y^2=p.}$
If ${p_1=1 }$ , then ${x=t, y=1}$ satisfy ${x^2+y^2=p.}$

Proof:

$\displaystyle \frac{p}{w}=\left[a_{0} ; a_{1}, a_{2}, \cdots a_{n}\right]=\frac{p_{n}}{q_{n}}$

$\displaystyle p_{n-1} \cdot q_{n}-p_{n} \cdot q_{n-1}=(-1)^{n}=-1$

$\displaystyle 1=p_{n} \cdot q_{n-1}-p_{n-1} \cdot q_{n}$

$\displaystyle \begin{aligned} &q_{n}^{2}+p_{n} \cdot q_{n-1}-p_{n-1} \cdot q_{n}=v \cdot p_{n}\\ &q_{n} \cdot\left(q_{n}-p_{n-1}\right)=p_{n} \cdot\left(v-q_{n-1}\right) \end{aligned}$

$\displaystyle p_{n} |\left(q_{n}-p_{n-1}\right)$

$\displaystyle \begin{aligned} &p_{n}>q_{n}>0\\ &p_{n}=a_{n} \cdot p_{n-1}+p_{n-2}>p_{n-1}>0 \end{aligned}$

Therefore

$\displaystyle q_{n}-p_{n-1}=0$

$\displaystyle \frac{p_{n}}{p_{n-1}}=\frac{p_{n}}{q_{n}}=\left[a_{0} ; a_{1}, \cdots a_{n}\right]$

$\displaystyle p_{n}=a_{n} \cdot p_{n-1}+p_{n-2}$

$\displaystyle \begin{aligned} \frac{p_{n}}{p_{n-1}} &=a_{n}+\frac{p_{n-2}}{p_{n-1}} \\ \frac{p_{n-1}}{p_{n-2}} &=a_{n-1}+\frac{p_{n-3}}{p_{n-2}} \end{aligned}$

So we get

$\displaystyle \frac{p_{n}}{p_{n-1}}=\left[a_{n} ; a_{n-1}, \cdots, a_{1}, a_{0}\right]$

$\displaystyle \left[a_{0} ; \cdots, a_{n}\right]=\left[a_{n} ; \cdots, a_{0}\right]$

Hence we see the palindromic behaviour

$\displaystyle \frac{p}{t}=\left[a_{0} ; a_{1}, \ldots, a_{m}, a_{m}, \ldots, a_{1}, a_{0}\right]$

If ${p_1=1}$ , then ${p=t \cdot a_{0}+1.}$
Therefore ${\frac{p}{w}=\left[a_{0} ; t \right]=\left[a_{0} ; a_0 \right]}$ so ${t=a_{0}.}$
${p=t^{2}+1.}$

$\displaystyle \frac{p}{t}=\left[a_{0} ; a_{1}, \cdots, a_{k}, a_{k}, \cdots, a_{0}\right]=\frac{p_{2 k+1}}{p_{2 k}}$

By recursive relations,

$\displaystyle \begin{aligned} &p=p_{2k+1}=a_{0} \cdot p_{2k}+p_{2 k-1} =a_{0} \cdot t+p_{2 k-1}\\ &t=p_{2k}=a_{1} \cdot p_{2 k-1}+p_{2 k-2} \end{aligned}$

$\displaystyle p_s =[[a_0, a_1, a_2, \cdots a_s]] =\left|\begin{array}{cccccc}a_{0} & 1 & 0 & \cdots & 0 & 0 \\ -1 & a_{1} & 1 & \cdots & 0 & 0 \\ 0 & -1 & a_{2} & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & a_{s-1} & 1 \\ 0 & 0 & 0 & \cdots & -1 & a_{s}\end{array}\right|$

$\displaystyle q_s = [[a_1, a_2, a_3, \cdots a_{s+1}]]= \left|\begin{array}{cccccc}a_{1} & 1 & 0 & \cdots & 0 & 0 \\ -1 & a_{2} & 1 & \cdots & 0 & 0 \\ 0 & -1 & a_{3} & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & a_{s} & 1 \\ 0 & 0 & 0 & \cdots & -1 & a_{s+1}\end{array}\right|$

We have

$\displaystyle [[b_0, b_1, b_2, \cdots b_s]] = [b_s, b_{s-1}, \cdots b_1, b_0]]$

Expanding the determinants, we see

$\displaystyle \begin{aligned} \left[[q_{1}, \cdots, q_{s-1}, q_{s}, q_{s+1}, q_{s+2}, \cdots, q_{n}\right]]=\left[[q_{1}, \cdots, q_{s-1}, q_{s}\right]]\left[[q_{s+1}, q_{s+2}, \cdots, q_{n}\right]] \\ +\left[[q_{1}, \cdots, q_{s-1}\right]]\left[[q_{s+2}, \cdots, q_{n}\right]] \end{aligned}$

Therefore

$\displaystyle p=p_{2k+1}=\left[[a_{0} ,a_{1}, \cdots, a_{k}, a_{k}, \cdots, a_{0}\right]]$

$\displaystyle = \left[[a_{0} ,a_{1}, \cdots, a_{k}\right]] \left[[a_{k}, \cdots, a_{0}\right]] + \left[[a_{0} ,a_{1}, \cdots, a_{k-1}\right]] \left[[a_{k+1}, \cdots, a_{0}\right]]$

$\displaystyle = \left[[a_{0} ,a_{1}, \cdots, a_{k}\right]] \left[[a_{0} ,a_{1}, \cdots, a_{k}\right]] + \left[[a_{0} ,a_{1}, \cdots, a_{k-1}\right]] \left[[a_{0} ,a_{1}, \cdots, a_{k-1}\right]]$

$\displaystyle =p_k^2+p_{k-1}^2$

(All of these ideas are related in some sense to Euclidean Algorithm in Gaussian integers, showing class number one for binary quadratic forms of discriminant ${-4}$ )

https://www.ams.org/journals/mcom/1972-26-120/S0025-5718-1972-0314745-6/S0025-5718-1972-0314745-6.pdf

Share this:

Related

Leave a comment Cancel reply