%\batchmode
\documentclass[12pt]{article}
\topmargin -0.5in
\pagestyle{empty}
\oddsidemargin 0pt
\textwidth 6.7in
\textheight 9.5in
\newcommand{\bigfrac}[2]{\frac{\textstyle #1}{\textstyle #2}}
   	\def\bbd#1{\leavevmode\setbox0=\hbox{#1}%
   	\kern-.025em\copy0 \kern-\wd0
   	\kern .05em\copy0 \kern-\wd0
  	\kern-.025em\raise.0433em\box0
  	}
   	\def\nexto{\kern -0.54em}
    	\def\DN{ \mbox{\rm {I\ \nexto N}} }
    	\def\DZ{ \mbox{\rm Z \kern -0.82em Z} }
    	\def\DC{ \mbox{\rm\hbox{C \kern-0.8em\raise0.2ex
    	\hbox{\vrule height5.4pt width0.7pt} \kern0.45em}} }
    	\def\DQ{ \mbox{\rm\hbox{Q \kern-0.85em\raise0.25ex
    	\hbox{\vrule height5.4pt width0.7pt} \kern0.45em}} }
    	\def\DP{ \mbox{\rm\hbox{P\kern-0.75em
	\hbox{\vrule height9pt width0.7pt} \kern0.45em}} }
	 \newcommand{\mat}[2]{\left(
    \begin{array}{*{#1}{c}}#2\end{array}\right)}
    \newcommand{\matr}[2]{\left(
    \begin{array}{*{#1}{r}}#2\end{array}\right)}
    \newcommand{\dat}[2]{\left|
    \begin{array}{*{#1}{c}}#2\end{array}\right|}


\begin{document}

	\begin{center}
{\bf $\stackrel{\mbox{MA330}}{Sathaye}$
\hfill Note on Chakrav\={a}la Method of Bh\={a}skara \hfill Edited \today  \ \  }
	\end{center}
\hfill \rule{6in}{0.01in}\hfill

We describe below a new technique inspired by the historical works of
Bh\={a}skara/Brahmagupta for the solution in positive integers of the
equation $$x^2-Dy^2=\pm 1.$$
where $D$ is a given positive integer which is not a complete square.
\begin{enumerate}
\item[\bf Notation]
We shall work in the field $F=\DQ(\sqrt{D})$ where $\DQ$ is the usual field of
rational numbers.


For convenience, we shall write a typical element
$a+b\sqrt{D}\in F$ where $a,b\in \DQ$ as a pair $(a,b)$ and by its norm we
shall mean $a^2-Db^2$ and we shall write it as $||(a,b)||_D$ or just $||(a,b)||$ $D$ is already fixed.

It might be more convenient to name a Brahmagupta triple for $D$ to be 
$<a,b,s>_D$ where $s=a^2-Db^2$. As above, we can drop $D$ from the notation if it is already fixed.

{\bf Convention:}Even though these concepts are defined for rational numbers, we generally assume that the entries are integers, because we are ultimately interested in integral solutions only.


Thus, our problem is to find all elements of norm $\pm 1$ and this set
is known to form the group of units in the ring $\DZ[\sqrt{D}]$ of
elements $(a,b)$ with $a,b\in \DZ$-the ring of integers.

A reader unfamiliar with this terminology can still follow the rest of
the work!

{\bf Homework exercises:}
\begin{enumerate}
\item Suppose $t_1:=<a_1,b_1,s_1>_D$ and $t_2:=<a_2,b_2,s_2>_D$ be two Brahmagupta triples. Define the Brahmagupta product (bh\={a}van\={a}) by:
$t_1*t_2 = <a,b,s>_D$ where 
$$a=a_1a_2+Db_1b_2, b=a_1b_2+a_2b_1 \mbox{ and } s=s_1s_2.$$

Prove that $s=||(a,b)||$.

\item Suppose that $<a,b,s>_D$ is a Brahmagupta triple. If an integer $m$ divides both $b$ and $s$, then show that $m$ divides $a$ as well. Moreover, we can deduce that  $<a/m,b/m,s/m^2>_D$ is a Brahmagupta triple (of integers).

We may call this the $m$-reduction of $<a,b,s>_D$.

\item Suppose that $<a,b,s>_D$ is a Brahmagupta triple (of integers) and $m$ divides $s$, then there is a Brahmagupta triple $<p,1,r>_D$ such that $a+bp$ is divisible by $m$. Moreover, it is possible modify $p$ such that 
$r=||(p,1)||_D$ is as small as possible.


 
\end{enumerate}
\item[\bf Method]
We now describe the steps.

\begin{enumerate}
\item[\bf Choose start:]
Choose a convenient pair $(a,1)$ such that the norm $||(a,1)||=
a^2-D$ is as small
as possible {\bf in the absolute value.} You simply need to compare the floor and the
ceiling of $\sqrt{D}$. Thus for $D=43$ we try $a=6,7$. The resulting
norms are $6^2-43 = -7$ and $7^2-43=6$. Since $|6|<|-7|$ we start with
$(7,1)$.
As another example, for $D=53$ we try $a=7,8$ and pick $7$ with norm $-4$
rather than $8$ with norm $11$.
We record the first pair, its norm and its `` extended norm ''.
For the first pair the extended norm is the same as the norm.

Now, we set $D=43$ we write:
$$\begin{array}{l|c}
\mbox{pair} &(7,1) \\\mbox{norm }& 6 \\\mbox{extended~norm}& 6
\end{array}
$$

\item[\bf Choose second:] Let $h$ be the absolute value of the extended 
norm of the first pair $(a,1)$
Choose an integer  $b$ such that
$$a+b \equiv 0 \pmod{h} \mbox{ and } (b,1) \mbox{ has minimal norm. }$$
Thus, we solve $a+b=7+b \equiv 5 \pmod{6}$. The value of
$b$ is chosen from the sequence $5,11,17,\cdots$ and clearly $5$ is a
winner!
The norm of $(5,1)$ is $25-43 =-18$. It is no accident that it is
divisible by $6$. This can be proved!{ \it \bf  Challenge: How?}

We shall record the leftover part of its norm as the extended norm, namely $h=\frac{-18}{6}=-3$.

So our record is now:
$$\begin{array}{l|c|c}
\mbox{pair }& (7,1) & (5,1) \\ 
\mbox{norm } & 6 & -18 \\ 
\mbox{extended ~ norm} & 6 & -3 \\
\end{array}
$$



\item[\bf Continue:] Now we repeat the above step by setting $a=5$ and
$h=3$. The choices for $b$ are $1,4,7,10,\cdots$ and the winner again
will be the one closest to the $\sqrt{D}=\sqrt{43}$. Now $b=7$ is the
winner with the norm of $(7,1)$ being $7^2-43=6$. Again, it is divisible
by $-3$ and the quotient is $h=-2$, our next extended norm. So our record is, now,
$$\begin{array}{l|c|c|c}
\mbox{pair } & (7,1) & (5,1) & (7,1) \\ 
\mbox{norm } & 6 & -18 & 6 \\
\mbox{extended ~ norm} & 6 & -3 & -2 \\
\end{array}
$$

To repeat the step, we take $a=7,h=-2$ and deduce $b=1,3,5,7,9,\cdots$
with the clear winner $7$. So the new display is:
$$\begin{array}{l|c|c|c|c}
\mbox{pair } &(7,1) & (5,1) & (7,1) & (7,1) \\
\mbox{norm } & 6 & -18 & 6 & 6 \\ 
\mbox{extended ~ norm} & 6 & -3 & -2 & -3 \\
\end{array}
$$

\item[\bf Stop:]
Verify that by continuing this way, we get:

$$\begin{array}{l|c|c|c|c|c|c|c}
\mbox{pair} &(7,1) & (5,1) & (7,1) & (7,1) & (5,1) & (7,1) \\ 
\mbox{norm } & 6 & -18 & 6 & 6  & -18 & 6 \\ 
\mbox{extended ~ norm} & 6 & -3 & -2 & -3 & 6 & 1 \\
\end{array}
$$

When $h$ becomes $\pm 1$ we stop!

\item[\bf Conclusion:] We have the necessary information to find our
$x,y$. We first multiply the various numbers in our first row in the
field $F$ and notice that at each stage certain integers can be
factored. We throw away these common factors. Here are the explicit steps:

$$\begin{array}{c|c|c|l}
\mbox{number } & \mbox{ product} & \mbox{ Factor out $h$ } & \mbox{
The extended norm $h$.} \\
7+\sqrt{D} & 7+\sqrt{D}  & & \\
(5+\sqrt{D}) & 78+12 \sqrt{D} & 13+2 \sqrt{D} & \mbox{$h=6$ }\\
(7+\sqrt{D}) & 177+27\sqrt{D} & -(59+9\sqrt{D}) & \mbox{$h=-3$} \\
(7+\sqrt{D}) & -(800+122\sqrt{D}) & 400+61\sqrt{D} & \mbox{$h= -2$}\\
(5+\sqrt{D}) & 4623+705 \sqrt{D} & -(1541+235 \sqrt{D}) & \mbox{$h=-3$}\\
(7+\sqrt{D}) & -(20892+3186 \sqrt{D}) & -(3482+531 \sqrt{D}) & \mbox{$h=6$}\\
\end{array}
$$

Our answer is $x=-3482, y=-531$ and hence also $x=3482, y=531$.


How do we know that we are done? We multiplied the pairs in the top row
whose norms were at the bottom in two parts.
Thus the norm of the whole product is
$$(6)(-18)(6)(6)(-18)(6) = (6)[(6)(-3)][(-3)(-2)][(-2)(-3)][(-3)(6)][(6)(1)]= (6\cdot 3 \cdot 2 \cdot 3
\cdot 6)^2.$$

But we clearly divided by the same amount due to factoring, so the
resulting norm is $1$.


\item[\bf Modification] Clearly, it is wasteful to write the pairs on
top, since the second number is always $1$.
So, we shall shorten our display to:

$$\begin{array}{c|c|c|c|c|c|c}
7 & 5 & 7 & 7 & 5 & 7 \\ 
6 & -18 & 6 & 6  & -18 & 6 \\
6 & -3 & -2 & -3 & 6 & 1 \\
\end{array}
$$
\end{enumerate}



\end{enumerate}

\vspace*{\fill}
\end{document}



