% A LaTeX document
% March 10, 2003
\documentclass[11pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}


%\headheight=7pt
%\textheight=8in
\oddsidemargin=.1in
%\topmargin=14pt
\textwidth=6.1in
\evensidemargin=.1in


\newtheorem{lemma}{Lemma}%[section] 
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{corollary}[lemma]{Corollary} 
\newtheorem{conjecture}[lemma]{Conjecture}
\newtheorem{identity}{Identity} 

\newcommand{\ignore}[1]{}
\def\s{\atopwithdelims[]}
\def\S{\atopwithdelims\{\}}
\def\zbar{\overline z}
\def\rhobar{\overline \rho}
\def\ree{\mbox{Re}}
\def\imm{\mbox{Im}}
\def\zz{\zbar z}

\begin{document} 

%double-spacing command here
%\baselineskip=.25in

\begin{center}
\Large 
% TITLE GOES HERE
{\bf Pythagorean Primes and Palindromic Continued Fractions}
\end{center}

\begin{center}
Arthur T. Benjamin and Doron Zeilberger\\
\end{center}

\medskip


In this note, we prove that every prime of the form $4m+1$ is the sum
of the squares of two positive integers in a unique way. Our proof is
based on elementary combinatorial properties of continued fractions.
It uses an idea by Henry J. S.  Smith (\cite{Chrystal},
\cite{Dickson}, and \cite{Smith}) most recently described in
\cite{Clarke} (which provides a new proof of uniqueness and reprints
Smith's paper in the original Latin).  Smith's proof makes heavy use
of nontrivial properties of determinants. Our purely combinatorial
proof is self-contained and elementary.

For $n\geq 1$ and positive integers $a_0,\ldots,a_n$, let
$[a_0,\ldots,a_n]$ denote the finite continued fraction  
\begin{equation}
a_0 + \frac{1}{\textstyle a_1 + \frac{1}{\textstyle a_2 + \frac{1}{\textstyle \ddots +  \frac{1}{a_n}}}},
\end{equation}
which simplifies to a unique rational number $r/s >1$ in lowest
terms. Conversely, for every rational number $r/s >1$, there is a
unique continued fraction $[a_0,\ldots,a_n]=r/s$ where $a_0\geq
1,\ldots a_{n-1}\geq 1$, and $a_n\geq 2$. (It happens that $r/s$ has
one other continued fraction representation, namely
$[a_0,\ldots,a_{n-1},a_n -1,1]$, but we will not use this.)

Continued fractions have a simple combinatorial interpretation, which
we describe here. For positive numbers $a_0,\ldots,a_n$, define the
{\it continuant} $K(a_0,\ldots,a_n)$ to be the number of ways to tile
a strip of length $n$ with dominoes (of length two) and {\em 
stackable} squares (of length one). For $1 \leq i \leq n$, if cell $i$
is covered by a square, then 
the number of squares that
may be stacked on the $i$th cell is at most $a_i$; if cell $i$ is
covered by a domino, then nothing is stacked on top of that domino.


For example, $K(3,7,15)=333$ since a strip of length three can be
tiled as ``domino-square'' in 15 ways (by choosing how many squares to
stack on the third cell) , as ``square-domino'' in 3 ways (by choosing
how many squares to stack on the first cell), or as
``square-square-square'' in $3\times 7\times 15 = 315$ ways (by
choosing how many squares to stack on each cell). 
Thus for nonnegative integers $a$ and $b$, 
\begin{equation}
K(a)=a, \ \ \ \ \ \ K(a,b) = ab+1.
\label{ic}
\end{equation}
For example, $K(7,15) = 106.$ For the empty set, we define $K(\ ) = 1$.
For $n\geq 2$, 
\begin{equation}
K(a_0,\ldots,a_n) = a_nK(a_0,\ldots,a_{n-1}) + K(a_0,\ldots,a_{n-2}),
\label{lasttile}
\end{equation}
since the first term counts tilings that end with a stack of squares
and the second term counts those that end with a domino. More
generally, observe that for $n\geq 1$ and $0\leq\ell\leq n-1$,
\begin{equation}
K(a_0,\ldots,a_n) = 
K(a_0,\ldots,a_{\ell})K(a_{\ell +1},\ldots,a_n) + K(a_0,\ldots,a_{\ell -1})K(a_{\ell +2},\ldots,a_n).
\label{breakable}
\end{equation}
The first summand counts tilings that do not have a domino covering cells $\ell$ and $\ell +1$, while the second summand counts those that do.

Finally, we observe that for any nonnegative $a_0,\ldots,a_n$,
\begin{equation}
K(a_n,\ldots,a_0) = K(a_0,\ldots,a_n) 
\label{reversible}
\end{equation}
since any length $n$ tiling that satisfies the conditions on the right (at most
$a_i$ squares stacked on cell $i$) can be
reversed to satisfy the tiling conditions on the left (at most $a_{n-i}$
squares stacked on cell $i$), and vice versa. 

Using the initial conditions and recurrence in equations (\ref{ic}) and
(\ref{lasttile}),  it follows that 
\begin{equation}
[a_0,\ldots,a_n] = \frac{K(a_0,\ldots,a_n)}{K(a_1,\ldots,a_n)},
\label{cf}
\end{equation}
in lowest terms. 
(See \cite{book} or \cite{Mag} for more details.) 
That is, if the continued fraction
$[a_0,\ldots,a_n] = \frac{p_n}{q_n},$
in lowest terms, then 
$p_n = K(a_0,\ldots,a_n)$
and 
$q_n = K(a_1,\ldots,a_n).$
Thus, for example, the continued fraction 
$[3,7,15] = K(3,7,15)/K(7,15) = 333/106.$ 

Now suppose that $p=4m+1$ is prime. We shall consider the continued fraction
expansions of the numbers 
$p/1, p/2, \ldots, p/(2m).$ For each $j$ between $1$ and $2m$, we have
$p/j > 2$ and is in lowest terms. 
Thus $p/j=[a_0,\ldots,a_n]$ where $a_0\geq 2$ and $a_n\geq 2$.
By equations
(\ref{cf}) and (\ref{reversible}), 
$$p = K(a_0,\ldots,a_n) = K(a_n,\ldots,a_0).$$
Thus $[a_n,\ldots,a_0]$ also has numerator $p$, and since $a_n\geq 2$,
$[a_n,\ldots,a_0] = p/i$ for some
$i$ between $1$ and $2m$. Thus each fraction $p/j$ can be paired up with its
``reversed'' fraction $p/i$. Now $p/1 = [p]$ is {\em palindromic}; it
is its own reversal. Thus since $2m$ is even, there must be at least
one other fraction $p/j^*$ that is palindromic. That is, for some  
$j^*$ between $2$ and $2m$,
$$[a_0,\ldots,a_{n^*}] = p/j^* = [a_{n^*},\ldots,a_0].$$
For example, when $p=5$, $5/1=[5]$ and $5/2=[2,2]$ are both 
palindromic. When $p=13$, $13/1 = [13]$, $13/2= [6,2]$, $13/3 =
[4,3]$, $13/4 = [3,4]$, $13/5 = [2,1,1,2]$, $13/6 = [2,6]$; so $13/1$
and $13/5$ are palindromic. 

We claim that $n^*$ must be even. For suppose, to the contrary, that 
$n^* = 2\ell + 1$, for some $\ell \geq 0$. 
Then $p/j^* = [a_0,\ldots,a_{\ell},a_{\ell+1},a_{\ell},\ldots,a_0].$ 
Thus by applying equations (\ref{cf}), (\ref{breakable}), and
(\ref{reversible}), we have 
\begin{eqnarray*}
p & = & K(a_0,\ldots,a_{\ell},a_{\ell+1},a_{\ell},\ldots,a_0)\\ & = & 
K(a_0,\ldots,a_{\ell})K(a_{\ell+1},\ldots,a_0)+K(a_0,\ldots,a_{\ell-1})K(a_{\ell},\ldots,a_0)\\
& = & K(a_0,\ldots,a_{\ell})[(K(a_0,\ldots,a_{\ell+1})+ K(a_0,\ldots,a_{\ell-1})].
\end{eqnarray*}
But then $p$ is composite (both factors are at least two, since $a_0
\geq 2$), which is a contradiction. 

Thus $n^* = 2\ell$ for some $\ell\geq 1$. Consequently, $p/j^* =
[a_0,\ldots,a_l,a_l,\ldots,a_0],$ 
and 
\begin{eqnarray*}
p & = & K(a_0,\ldots,a_{\ell},a_{\ell},\ldots,a_0)\\ & = & 
K(a_0,\ldots,a_{\ell})K(a_{\ell},\ldots,a_0)+K(a_0,\ldots,a_{\ell-1})K(a_{\ell-1},\ldots,a_0)\\
& = & (K(a_0,\ldots,a_{\ell}))^2 + (K(a_0,\ldots,a_{\ell-1}))^2
\end{eqnarray*}
is the sum of two squares, as desired.

For example, when $p=13$, the palindromic $13/5$ leads to
$$13 = K(2,1,1,2) = K(2,1)K(1,2) + K(2)K(2) = 3^2 + 2^2.$$ 
For a larger example, when $p=1069$, the palindromic $1069/249 =
[4,3,2,2,3,4]$ leads to $$1069 = K(4,3,2,2,3,4) = (K(4,3,2))^2 +
(K(4,3))^2 = 30^2 + 13^2.$$ 

Following the strategy in \cite{Clarke}, we 
combinatorially prove uniqueness of the sum of squares using
one more elementary fact about continued
fractions: If $[a_0,\ldots,a_n]= p_n/q_n$ in lowest terms, then for
$n\geq 2$, 
$$\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}=\frac{(-1)^n}{q_nq_{n-1}}.$$
Equivalently, $p_nq_{n-1} - p_{n-1}q_n = (-1)^n,$ or by equation
(\ref{cf}), for $n\geq 2$,
\begin{equation}
K(a_0,\ldots,a_n)K(a_1,\ldots,a_{n-1}) -
K(a_0,\ldots,a_{n-1})K(a_1,\ldots,a_n) = (-1)^n.
\label{CassiniCF}
\end{equation}
For a direct combinatorial proof of equation (\ref{CassiniCF}), see
\cite{book} or \cite{Mag}.

Now suppose that $p=r^2+s^2$ and $p=u^2+v^2$ for positive integers
$r>s$ and $u>v$. Since $p$ is prime, $\gcd(r,s)=1=\gcd(u,v)$.
Thus $r/s$ and $u/v$ are fractions in lowest terms, and there exist
unique positive integers $r_0,\ldots,r_t$ and $u_0,\ldots,u_w$ such
that $r/s = [r_0,\ldots,r_t]$ and $u/v = [u_0,\ldots,u_w]$, where
$r_t\geq 2$ and $u_w\geq 2$.

Hence, by equation (\ref{cf}),
$$ \frac{r}{s} = \frac{K(r_0,\ldots,r_t)}{K(r_1,\ldots,r_t)}$$
in lowest terms. Now by equations (\ref{breakable}) and (\ref{reversible}),
$$p=r^2+s^2=K(r_t,\ldots,r_0)K(r_0,\ldots,r_t)+
K(r_t,\ldots,r_1)K(r_1,\ldots,r_t) =
K(r_t,\ldots,r_0,r_0,\ldots,r_t).$$

Now let $x=K(r_t,\ldots,r_0,r_0\ldots,r_{t-1}).$
By equation (\ref{lasttile}),
$$p=K(r_t,\ldots,r_0,r_0,\ldots,r_{t}) = 
x r_t+K(r_t,\ldots,r_0,r_0\ldots,r_{t-2})\geq 2x+1.$$ 
Thus $2\leq x \leq (p-1)/2$. 
Also, by equation (\ref{CassiniCF}),
$$K(r_t,\ldots,r_0,r_0\ldots,r_{t})K(r_{t-1},\ldots,r_0,r_0\ldots,r_{t-1})
-K(r_t,\ldots,r_0,r_0\ldots,r_{t-1})K(r_{t-1},\ldots,r_0,r_0\ldots,r_{t})$$
equals $(-1)^{2t} = 1.$
Hence, $pK(r_{t-1},\ldots,r_0,r_0\ldots,r_{t-1}) -x^2 = 1$, and
therefore $x$ satisfies $x^2\equiv -1 \pmod p$.

By the same argument, we also have
$u/v=K(u_0\ldots,u_w)/K(u_1\ldots,u_w)$ in lowest terms,
$p= K[u_w,\ldots,u_0,u_0,\ldots,u_w]$, and
$y=K(u_w,\ldots,u_0,u_0,\ldots,u_{w-1})$
satisfies $2\leq y\leq (p-1)/2$ and $y^2\equiv -1 \pmod p$.

Thus $x^2\equiv y^2 \pmod p$, and so $p$ divides
$x^2-y^2=(x+y)(x-y)$. Since $p$ is prime it follows that $x\equiv y$
or $x\equiv -y \pmod p$. But since $x$ and $y$ are both between $2$
and $(p-1)/2$, we must have $x=y$. But then, by equation (\ref{cf}),
the continued fraction 
\begin{eqnarray*}
[r_t,\ldots,r_0,r_0,\ldots,r_t] & = &
\frac{K(r_t,\ldots,r_0,r_0,\ldots r_t)}{K(r_{t-1},\ldots,r_0,r_0,\ldots r_t)}
= \frac{p}{x} = \frac{p}{y}\\
& = & 
\frac{K(u_w,\ldots,u_0,u_0,\ldots u_w)}{K(u_{w-1},\ldots,u_0,u_0,\ldots u_w)}
= [u_w,\ldots,u_0,u_0,\ldots, u_w],
\end{eqnarray*}
and by the uniqueness of finite continued fraction representations
(with $r_t\geq 2$ and $u_w\geq 2$), we must have 
$t=w$ and $r_i=u_i$ for all $1\leq i\leq t$. Consequently,
$$\frac{r}{s}=[r_0,\ldots,r_t] = [u_0,\ldots,u_w] = \frac{u}{v}$$
in lowest terms. Thus $r=u$ and $s=v$ as desired.

In summary, every prime number $p=4m+1$ is the unique sum of two
squares as follows. Let $x$ be the unique solution to $x^2\equiv -1
\pmod p$, where $2\leq x \leq 2m$. [By Wilson's Theorem, $x$
will be the smallest positive integer congruent to $\pm (2m)! \pmod
p$. We note that if $a$ is any quadratic nonresidue of $p$, then $x$
can be efficiently calculated. From Euler's criterion, $a^{(p-1)/2}
\equiv -1 \pmod p$. Thus we can set $x$ equal to the smallest positive
integer congruent to $\pm a^{(p-1)/4} \pmod p.$]
Then $p/x$ has palindromic continued fraction representation
$[r_t,\ldots,r_0,r_0,\ldots,r_t]$, and $[r_0,\ldots,r_t]= r/s$, where
$r^2 + s^2 = p$.


\begin{thebibliography}{AA}

\bibitem{book} Arthur T. Benjamin and Jennifer J. Quinn, {\it Proofs
    that Really Count: The Art of Combinatorial Proof}, MAA,
  Washington, DC, 2003. 

\bibitem{Mag} Arthur T. Benjamin, Jennifer J. Quinn, and Francis Edward Su, Counting on Continued Fractions,
{\em Mathematics Magazine,} Vol 73, No. 2, pp. 98-104, 2000. 

\bibitem{Chrystal} G. Chrystal, {\em Algebra: an elementary text-book
    for the higher classes of secondary schools and for colleges, Part
    II}, page 499, reprinted by Chelsea, N.Y., N.Y., 1964. 

\bibitem{Clarke} F. W. Clarke, W. N. Everitt, L. L. Littlejohn, and
  S. J. R. Vorster, H. J. S. Smith and the Fermat Two Squares Theorem,
  {\it Amer. Math. Monthly} {\bf 106} (1999) 652--665.

\bibitem{Dickson} L. E. Dickson, {\em History of the Theory of Numbers,
  Vol. II}, American Mathematical Society, Providence, pp. 240-241.

\bibitem{Smith} Henry J. S. Smith, De Compositione Numerorum Primorum
  $4\lambda+1$ Ex Duobus Quardatis, {\it Crelle's Journal} V. 50
    (1855), 91--92. 

\end{thebibliography}


\medskip
{\it
\noindent
Harvey Mudd College \\
Claremont, CA 91711\\
{\tt benjamin@math.hmc.edu}
}

\medskip
{\it
\noindent
Rutgers University \\
Piscataway, NJ 08854-8019\\
{\tt zeilberg@math.rutgers.edu}
}


\end{document}

