
%%%%%
%\includegraphics[width=2.05in,height=1.39in]{welcome.bmp}
%\input epsf
%\epsfverbosetrue
%\def\pict#1#2#3{\epsfxsize=#1in \epsfysize=#2in \epsffile{#3.eps}}
\documentclass[12pt]{article}
%\usepackage{amssymb,amsmath,amscd}
\usepackage{graphicx}
\setlength{\oddsidemargin}{-.5in}
\setlength{\evensidemargin}{-.5in}
\setlength{\textwidth}{7.25in}
\topmargin  -.7in
\textheight 9.45in
\newcommand{\bigfrac}[2]{\frac{\textstyle #1}{\textstyle #2}}
\newcommand{\starttest}{\begin{enumerate}}
\newcommand{\nextpage}{\vspace*{\fill}\newpage}

\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|}
\newcommand{\lcm}{\mbox{lcm}}
\begin{document}

%\thispagestyle{empty}
\begin{center}
{\bf $\stackrel{\mbox{MA330}}{Sathaye}$ \hfill {\bf Better Division Algorithm } \hfill \ \  }
\end{center}

Given below is a convenient version of the well known Euclidean
algorithm which is easy to use and gives several useful conclusions
fast.

This version is from a Mathematical section of a work on Astronomy by an
astronomer \={A}ryabha\d{t}a from India in the fifth century. The
suggested working presented here differs from the traditional
commentaries, but seems consistent with the original (very cryptic)
description.

Let us say we have to calculate the gcd of the numbers $a=414$ and $b=189$.
We also wish to solve the equation $ax-by = s$ in integers.

The work consists of three steps represented by the three matrices given
below. I will explain the work further down.
$$
A ~=~\matr{3}{steps & a_i & q_i \\\hline 
0 & 414 & *\\
1&  189 & 2 \\
2 & 36 & 5 \\
3 &  9 & 4 \\
4 & 0 & *\\}
~~~
B~=~ \matr{4}{
steps & x_i & a_i & q_i\\\hline
 0 & 11 & 414 & \\
 1 &  5 & 189 & 2 \\
 2 & 1 & 36 & 5 \\
 3 & 0 & 9 & 4 \\
 4 &1 & 0 & \\}
~~
C~=~\matr{5}{steps & t_i & x_i & a_i & q_i\\\hline
0 & 46 & 11 & 414 & * \\
1 &  21 & 5 & 189 & 2 \\
2 & 4 &  1 & 36 & 5 \\
3 &  1 & 0 & 9 & 4 \\
4 & 0 & 1 & 0 & * \\}
$$

Here are the details:
\begin{enumerate}
\item The matrix $A$ represents the basic algorithm of calculating successive remainders $a_i$ (similar to Euclid's algorithm), except for the extra record of the quotients $q_i$. You start with the
two numbers on top. Call them $a_0, a_1$ in our notation.
Divide the upper number $a_0$ by the one below $a_1$ and write
the remainder $a_2$ below. The quotient $q_1$  is recorded to the right of $a_1$. 

You continue
until you get a $0$ in the $a_i$ column. Here $a_4=0$.
The steps are numbered as $0,1,2,3,4$ for convenience of notation.
We let $n$ be the last step number (here $n=4$).
The $\gcd(a_0,a_1)$ is then given by $a_{n-1} = a_3 = 9$.


\item The matrix $B$ is obtained inserting a column of $x_i$, but starting from the bottom.  Thus we set  $x_4=1$ at the bottom.  Also the entry above is $x_3=0$. These are always fixed as $1,0$ in order.

To calculate the next $x_i$ above, the formula is 
$$x_{i-1} = x_i q_i + x_{i+1}.$$
Thus, 
$$x_2 = x_3 q_3 + x_4 = (0)(4)+1 =1.$$
Similarly, $x_1 = x_2q_2+x_3 = (1)(5)+0 = 5$.


The array $B$ is the main tool to write the $\gcd(a_0,a_1) = 9$ as a combination of $a_0,a_1$.

We claim and note the important property called $x$-identity: 
$$\det \matr{2}{x_i & a_i \\ x_{i+1} & a_{i+1}} = \pm \gcd(a_0,a_1).\eqno{\mbox{\bf HW1}} $$
This can be proved by {\bf decreasing induction} starting from $i=n-1$ down to $0$. 

\item The matrix $C$ is obtained by a process similar to the one in $B$,
except you start with $t_n=0$  and $t_{n-1}=1$. This explains the bottom two numbers $t_4=0$ and $t_3=1$.

We use a similar rule as in the case of $B$, namely:
$$t_{i-1} = t_i q_i + t_{i+1}.$$

We claim and note the similar $t$-identity:  
$$\det \matr{2}{t_i & a_i \\ t_{i+1} & a_{i+1}} = 0. \eqno{\mbox{\bf HW2}}$$
This also can be proved by {\bf decreasing induction} starting from $i=n-1$ down to $0$. 

\item As described above, we have $\gcd(414,189)=9$.
From the $x$-identity above, we have
$$\det \matr{2}{x_0 & a_0 \\ x_{1} & a_{1}} = 11(189)- 5(414) = \pm 9.$$
A simple check of the units digit shows the RHS to be $+9$.

Moreover, it is easy to deduce that 
$$(x_0+st_0)(a_1)-(x_1+st_1)(a_0) = \pm \gcd(a_0,a_1) \eqno{\mbox{\bf HW3}}$$
for {\bf any value of $\mathbf{s}$}.

Naturally, the sign is the same as determined by using the $x$-identity.

\item


In our example, this
becomes $$(11+46s)189 - (5+21s)414 =  9 $$
for any value of $s$.

\item The top two numbers $t_0, t_1$ are also useful, namely 
$$t_0 = \frac{a_0}{d} \mbox{ and } t_1 = \frac{a_1}{d}$$ where 
$d=\gcd(a_0,a_1)$. Prove this! \hfill {\bf HW4}

Thus $t_0=a_0/d = 414/9 = 46$ and $t_1=a_1/d = 189/9 = 21$ respectively. Thus the $\lcm(a_0,a_1)=t_0t_1d$


\item Now we solve the main problem that \={A}ryabha\d{t}a wanted to solve:
``How to write a desired integer $w$ as $w= x_0a_1 - x_1a_0$ for some integers $x_0,x_1$ and moreover, how to find all possible values of $x_0,x_1$ which satisfy this condition?'' 

We have three methods.

\item {\bf Method 1.} First, we remark that the desired $w$ must be a multiple of $d$, since both $a_0,a_1$ are a multiple of $d$.

Thus write $w=md$ and note that we do have a relation
$ \epsilon d = x_0a_1 - x_1a_0$ where $\epsilon = \pm 1$. 
This gives us a desired relation:
$$w=\left(\epsilon m x_0\right)a_1 - \left(\epsilon m  x_1\right) a_0 $$.

Using the most general solution above, we can even write:
$$w=\left(\epsilon m (x_0+st_0)\right)a_1 - \left(\epsilon m (x_1+st_1)\right) a_0 $$.

We can choose suitable values of $s$ so that the coefficients of $a_0$ and $a_1$ are both positive (or negative) as desired and moreover their absolute values are minimal.

See details below.


For our example, we have $\epsilon = 1$ and  we get 
$$(46s+11m)189 - (21s+5m)414 =  9m .$$

Thus if $w=54$ we set $m=6$ and

$$(46s+66)189 -  (21s+30m)414 = 54.$$
To find minimal positive solutions we may set $s=-1$ to yield $(20)189 - (9)414 = 54$.
The most general solution will become $(46s+20)189 - (21s+9)(414)=54$.

If, on the other hand, we desire a solution of the form 
$w=X(414)-Y(189)=54$ then we may take $s=-1$ to get 
$$(-26)(189) -(-12)(414) = 12(414)  -26(189) = 54.$$
This gives a new general solution:
$$w= (46s+12)(414)  -(21s+26)(189) = 54.$$

{\bf Method 2.} Here, we redo the process for finding $x_i$ by 
choosing suitable $x_n, x_{n-1}$ so that 
$$w=x_{n-1}a_n - x_na_{n-1} = x_{n-1}0-x_nd = -x_nd.$$
Thus, we can take $x_{n-1}=0$ and $x_n=m$.

Then we can repeat the original process so that we get our desired solution for the expression of $w$.

\item {\bf Original Method 3.} 
The original algorithm said that we need not go to the $a_n=0$, but may lift the solution from any convenient step (cleverly imagined!)

For instance, for $w=54$, we start by setting
$x_3=-1,x_2=2$.  The lifting process then gives:
$x_1 = x_2q_2+x_3 = (2)(6)+(-1)=9$ and $x_0 = x_1 q_1 + x_2 = (9)(2)+2 =20$.

We then have $(20)(189) - (9)(414) = 54$ as desired. 
The general solution is still $(46s+20)(189)-(21s+9)(414)$.
We may have to modify the signs as before.

\item First homework on this discussion is to provide proofs for the various statements marked as {\bf (HW)}above. 
These should be written out and submitted. They would be more appreciated, if typed.

Problems based on the above algorithms will be announced as a separate homework later.

\end{enumerate}

\end{document}
Having studied the process of solving ax-by=c you should solve the following
problems.
First five are routine problems, while the last two illustrate
the original applications.

\begin{enumerate}
\item Find a number (and all such positive numbers) which is divisible by $29$
after adding $2$ to it and also
divisible by $45$ after subtracting $7$ from it.

Do determine the smallest positive such number.

{\bf Hint: You need to solve the eqution $45a - 29 b =9$. Do analyze how this will
help you answer the question.}

\item Find a number divisible by $3$ after subtracting $5$ and divisible by $31$ after
subtracting $7$. ( A small variation from Bh\={a}skara I of 600 A.D.)

Do determine the smallest positive such number.

\item Find a number which has remainder $5$ when divided by $8$,
remainder $4$ when divide by $9$ and remainder $1$ when divided by $7$.

Do determine the smallest positive such number.

( A small variation from Bh\={a}skara I of 600 A.D.
 Bh\={a}skara I 600 A.D.)

\item Find a number which leaves a remainder $1$ when divided by $2,3,4,5$
or $6$ but is
divisible by $7$.

Do determine the smallest positive such number.

(\={A}ryabha\d{t}\={i}ya bh\={a}\d{s}ya 600 A.D. ,
Ibn-al-Haitam 1000 A.D., Fibonacci 1202 A.D.)

\item Suppose that if we count a set of objects by threes, then $2$ are left;
if we count by fives, then $3$ are left and if we count by sevens,
then $2$ are left.
How many objects are there?
(It is implied that you shuld find the smallest such positive number.
(Sunzi fifth century - the origin of the term  ``Chinese
Remainder Theorem!'')

\item The residue of the revolutions of Saturn is 24. Find the day number.
(laghubh\={a}skar\={i}ya  600 A.D.)
Explanation: Let $x$ be the day number or the number of days elapsed
since the beginning
of the yuga  (actually the current Kali yuga).
Yuga is a long period consisting of
$1,577,917,500$ civil days.
The planet Saturn makes $146,564$ revolutions in a yuga,
so makes $\frac{146,564}{1,577,917,500}$ revolutions in a day.
This number equals  $\frac{36,641}{394,479,375}$ .
The statement that the ``residue of revolutions is
$24$'' means that the fractional number of revolutions is
$\frac{24}{394,479,375}$.
So, your task is to find (smallest) number of days elapsed and
corresponding number of
revolutions from the beginning of this yuga!

By the way, this number of days in a yuga, which formally has
$432,000$ years gives
the average year as $365.259$ days in length.
The equation you get is
$$36,641x-24 = 394,479,375y$$
 where $y$ is the number of complete revolutions.

\item The Sun's mean position was obtained as longitude $148$ deg. $20$ min.
Calculate the day number. (Mah\={a}bh\={a}skar\={i}ya 600 A.D.)
and the number of revolutions of the Sun.

For Sun, the reduced number of daily revolutions comes out to be
$\frac{576}{210,389}$.
The fractional number of revolutions is calculated to be
$\frac{86,688}{210,389}$
after throwing away fractional part (less than 0.01) from the numerator.
Verify this from the longitude.

\end{enumerate}

\centerline{\hfill \bf \large Note on the time scale in Indian
tradition and astronomy.\hfill }
	

It was customary to do astronomical calculations on a grand scale.
One use of these calculations is that by axiom, the planetary positions
were $0$ in the beginning and their current values can be established by
knowing their periods. Of course, we know that
corrections are always needed,
to both the formulas and observations. Usually, these are handled by
special theories giving additional small variations in the answers.

Usually, the calculations start with the day number from the beginning of
the year with a given knowledge of the starting positions from record.

Here are some more amusing data.
The current yuga (Kali) has $432,000$ years and the previous three
(K\d{r}ta, Tret\={a} and Dv\={a}p\={a}ra ) were respectively $4,3,2$
times as long!
These four together are often called a (mah\={a})yuga.
The current one has only $5,104$ years elapsed.

The creator Brahm\={a} was approximately $8$ and a half of {\it his}
years old at the
beginning of the current yuga, which is declared as $26,782,530,123,179$ of
human years.

There are other variants of this huge number, though they all agree in the top
significant digits.

According to another school of thought, he is however, about $50$ years old.

How does a day of Brahm\={a} compare with the human scale of time?


A yuga (or mah\={a}yuga = the four together) is $4,320,000$ years.
A manu is $72$ such mah\={a}yugas. A kalpa is $14$ manus and evaluates
to $(14)(72)(4,320,000)=4,354,560,000$ years.
A day in the life of the creator is $2$ kalpas (one for the day and one for
the night!) or $8,709,120,000$ years! If you calculate a Brahm\={a}
year, it will come out to be $3,178,828,800,000$ human years and by this
count his $8$ and a half years match the given number. It is kind of
interesting to figure out the precise age in Brahm\={a} years, months,
days, hours etc.

It is amusing to compare this number with the number of years elapsed
since the big bang! The current theories seem to point to a number
between 11 and 20 billion years, so this number might match the
night and part of the day for Brahm\={a}!

So perhaps, the big bang happened at his late evening and it is now
daytime!


During religious rituals, it is customary to recite the current
year of the yuga,
the approximate age of Brahm\={a},
also the geographic position of the site, the current positions
of various planets etc.

It is unfortunate that the same care was rarely taken by
the authors of the books! So, Indian history has to be very vague about
the relative dates of various events and often it is hard to separate
facts from fiction!




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