\documentclass{beamer}[8pt]
\usepackage{beamerthemesplit}
\usetheme{Warsaw}
%\usepackage{verbatim}
\usepackage{pdfpages}
\usepackage{color}
\usepackage{graphicx}
\usepackage{fontspec}
\setmainfont[Script=Devanagari]{Sanskrit 2003}

\newfontfamily \dv[Script=Devanagari]{Sanskrit 2003}

\title{\textcolor{yellow}{Diophantine Equation}}
\author{Amba Kulkarni}
\institute{ University of Hyderabad}
\date{13th March 2018}

\begin{document}
\setbeamertemplate{footline}[frame number]
%===================================slide 1=========================%
\begin{frame}

\titlepage

\end{frame}
%============================================================%
\begin{frame}
\frametitle{Diophantine Equation}
A Diophantine Equation is a polynomimal equation in 2 or more unknowns such that all the unknown variables have integer solution.\\
\vspace{0.5cm}
There are fewer equations than unknown variables.\\
\vspace{0.5cm}
Diophantine refers to a Greek Mathematician of 3rd century Diophantus of Alexandria who studied such equations. He is the first who introduced symbols such as '=', '<',  and letter-based symbols etc. in Algebra.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Examples of Diophantine Equation}
\begin{tabular}{|l|l|} \hline\hline
ax+by=1 & Linear Diophantine Equation \\ \hline
$w^{3}+x^{3} = y^{3}+z^3$ & smallest solution: \\
& $12^3+1^3 = 9^3 + 10^3 = 1729$\\
& Hardy Ramanujan Number\\ \hline
$x^n+y^n=z^n$ & Fermat's Last Theorem \\
& (No solutions for n > 2)\\ \hline
$x^2 - ny^2 = \pm 1$ & Pell's Equation\\ \hline
$\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$& Erdo\"s-Straus Conjecture\\
& For every positive integer $n>1$ \\
& there exists a solution in x,y,z $>1$\\ \hline
$x^4+y^4+z^4=w^4$ & Elkies showed that there are many \\
&nontrivial solutions.\\ \hline \hline
\end{tabular}\\
\vspace{0.5cm}
Diophantine: adjective for nature of solutions to be Integer
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Diophantine Equation}
Diophantus: Investigated \textbf{a rational} solution\\
\vspace{0.5cm}
Indians: Investigated \textbf{all Integer} solutions of 1st and 2nd dgeree\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Diophantine: linear equations}
Aryabha\d{t}\d{t}a (5th AD) gave algorithm to solve linear equation.\\
This is briefly described in {\=A}ryabha\d{t}{\=\i}ya. This description is very incomprehensible.\\
\vspace{0.5cm}
Later Bhaskara -I (7th century) gave a detailed algorithm with several examples in {\=a}ryabha\d{t}{\=\i}yabh{\=a}\d{s}ya and gave the name \textit{ku\d{t}\d{t}aka}.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Diophantine: quadratic equations}
No general method is known to solve quadratic or higher order equations.\\
Pell's equation: $x^2-Dy^2=1$\\
\vspace{0.5cm}
Indians evolved an algorithm to solve these (during 7th to 11th century).\\
\vspace{0.5cm}
Systematic study of Diophantine equations in Europe began only in 17th century.\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Prayojana}
What motivated Indian to solve linear Diophantine equations?\\
\'{S}ulbasutras\\
Altar construction: Five layers of bricks with each layer having 21 bricks.\\
Total area: 1 square unit.\\
\vspace{0.5cm}
To have stability in structure, the cleavages between two adjacent bricks of two successive layers should not coincide.\\
\vspace{0.5cm}
Suppose a layer has $x$ bricks of $m^2$ area and $y$ bricks of $n^2$ area.\\ 
The problem reduces to solving simultaneous Diophantine equations\\
$x + y = 21$\\
$\frac{x}{m^2} + \frac{y}{n^2} = 1$\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Baudh{\=a}yana's solutions}
Suppose a layer has $x$ bricks of $m^2$ area and $y$ bricks of $n^2$ area.\\ 
$x + y = 21$\\
$\frac{x}{m^2} + \frac{y}{n^2} = 1$\\
\vspace{0.5cm}
There are two solutions for $(x,y,m,n)$ viz. $(16,5,6,3)$ and $(9,12,6,4)$.\\
\vspace{0.5cm}
Baudh{\=a}yana's Sulvasutra:\\
\vspace{0.5cm}
Three types of square bricks of length $\frac{1}{6}$, $\frac{1}{4}$, and $\frac{1}{3}$.\\
1st, 3rd and 5th layer: 9 bricks of length $\frac{1}{6}$ and 12 bricks of length $\frac{1}{4}$\\
2nd and 4th layer: 16 bricks of length $\frac{1}{6}$ and 5 bricks of length $\frac{1}{3}$\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Baudh{\=a}yana and {\=a}pastambha}
Construction of \'{s}yena citi (Falcon shaped Altar)\\
$x + y + z + u = 200$ and $\frac{x}{m} + \frac{y}{n} + \frac{z}{p} + \frac{u}{q} = 7\frac{1}{2}$.\\
\vspace{0.5cm}
$x + y + z + u +v = 200$ and $\frac{x}{m} + \frac{y}{n} + \frac{z}{p} + \frac{u}{q} + \frac{v}{r}= 7\frac{1}{2}$.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Aryabha\d{t}a's description}

adhik{\=a}grabh{\=a}gah{\=a}ra\d{m} chindy{\=a}d{\=u}n{\=a}grabh{\=a}gah{\=a}re\d{n}a\\
\'{s}e\d{s}a parasparabhakta\d{m} matigu\d{n}amagr{\=a}ntare k\d{s}iptam\\
adhauparigu\d{n}itamantyayug{\=u}n{\=a}gracchedabh{\=a}jite \'{s}e\d{s}a\\
m{\=a}dhik{\=a}gracchedagu\d{n}am dvicched{\=a}gramadhik{\=a}grayutam\\
%From https://en.wikipedia.org/wiki/Ku%E1%B9%AD%E1%B9%ADaka

\end{frame}
%============================================================%
\begin{frame}
\frametitle{Aryabha\d{t}a's description: English Translation}
%Translation by Bibhutibhushan Datta
Divide the divisor corresponding to the greater remainder by the divisor corresponding to the smalleer remainder. The residue (and the divisor corresponding to the smaller remainder) being mutually divided (until the remainder becomes zero), the last quotient should be multiplied by an optional integer and then added (in case the number of quotients of the mutual division is even) or subtracted (in case the number of quotients is odd) by the difference of the remainders. (Place the other quotients of the mutual division successively one below the other in a column; below them the result just obtained and underneath it the optional integer.) Any number below (that is, the penultimate) is multiplied by the one just above it and added by that just below it. Divide the last number (obtained so doing repeatedly) by the divisor corresponding to the smaller remainder; then multiply the residue by the divisor corresponding to the grater remainder and add the greater remainder. (The result will be) the number corresponding to the two divisors.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Aryabha\d{t}a's Formulation of Problem}
Following three problems are equivalent to the problem of solving a linear Diophantine equation.
\begin{itemize}
\item Find an integer which when divided by two given integers leave two given remainders.\\
Find N such that $N = ax + R_1 = by + R_2$
\item Find a number $x$ such that when multiplied by $a$ and incresed / decreased by $c$ is divisible by $b$.\\
$ax + c = by$ or $ax -c = by$.
\item Find two number $x$ and $y$ such that when multiplied by $a$ and $b$ give a constant difference $c$.\\
$ax-by=c$.
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{\'{s}lokas from Bh{\=a}skar{\=a}charya's b{\=\i}jaga\d{n}itam}
bh{\=a}jyo h{\=a}ra\d{h} k\d{s}epaka\d{h} ca-apavarta\d{h}\\
ken{\=a}py{\=a}dau sa\.mbhave ku\d{t}\d{t}ak{\=a}rtham\\
yena cchinnau bh{\=a}jyah{\=a}rau na tena\\
k\d{s}epa\'{s}etad du\d{s}\d{t}am-uddi\d{s}\d{t}am-eva\\
\vspace{0.5cm}
First the dividend(bh{\=a}jya = a), divisor(h{\=a}ra = b) and the constant(k\d{s}epaka)  should be simplified by dividing by the greatest common divisor, if any, for the solution of the ku\d{t}\d{t}aka $ax + c = by$\\
\vspace{0.5cm}
If it is not possible to divide the constant by the GCD of the dividend and divisor, such simplification is not possible.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{\'{s}lokas from Bh{\=a}skar{\=a}charya's b{\=\i}jaga\d{n}itam}
parasparam bh{\=a}jitayo\d{h} yayo\d{h} ya\d{h} \\
\'{s}e\d{s}a\d{h} tayo\d{h} sy{\=a}d apavartanam sa\d{h}\\
tena apavartena vibh{\=a}jitau yau tau \\
bh{\=a}jyah{\=a}rau d\d{r}\d{d}hsaj\~nakau sta\d{h}\\
mitho bhajetau d\d{r}\d{d}habh{\=a}jya harau \\
y{\=a}vat vibh{\=a}jye bhavat{\=\i}ha r{\=u}pam\\
phal{\=a}ni ada\d{h} ada\d{h} tad-adho nive\'{s}ya\d{h} \\
k\d{s}epa\d{h} thatha ante kha\.m upa-antimena\\
svordhe hate-antena yute tad antyam tyajew \\
muhu\d{h} sy{\=a}d iti r{\=a}\'{s} yugmam\\
{\=u}rdho vibh{\=a}jyena d\d{r}dhena ta\d{s}\d{t}a\d{h}\\
phalam gu\d{n}a\d{h} sy{\=a}d aparo hare\d{n}a\\
\vspace{0.5cm}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{\'{s}lokas from Bh{\=a}skar{\=a}charya's b{\=\i}jaga\d{n}itam}
From the mutual division of divisor and dividend what remains is the common factor. Dividing them by the common factor, the quotients left are called steady(d\d{r}\d{d}ha) coefficients. Mutually divide such simplified coefficients, till the remainder becomes unity.\\
\vspace{0.5cm}
Place the coefficients of mutual division one below the other and below them the constant and lastly zero to form a column. With the penultimate term of this column multiply the factor above and add the term below. The result should be used to replace the factor above. Delete the last term from the column and form the truncated column.\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{\'{s}lokas from Bh{\=a}skar{\=a}charya's b{\=\i}jaga\d{n}itam}
Continue this process till only two factors are left in the column. Reduce these numbers by dividing the top one by the dividend and the lower one by the divisor.\\
\vspace{0.5cm}
The remainders so left will be the values of Labdhi (y) and gu\d{n}a (x) respectively, subject to the conditions to be stated below.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{\'{s}lokas from Bh{\=a}skar{\=a}charya's b{\=\i}jaga\d{n}itam}
eva\.m tadeva atra yad{\=a} sam{\=a}pt{\=a}\d{h}\\
syu\d{h} labdaya\d{h} ced vi\d{s}m{\=a}\d{h} tad{\=a}n{\=\i}m\\
yath{\=a}gatau labdhi gu\d{n}au vi\'{s}dhyo\\
sva tatk\d{s}a\d{n}{\=a}t \'{s}\d{s}amitau tu tau sta\d{h}\\
\vspace{0.5cm}
In this manner, the results (x and y) obtained are true if the number of quotients (of mutual division) is even.\\
\vspace{0.5cm}
If the number of quotients is odd, the results (x and y) so obtained should be subtracted from the dividend and the divisor respectively and remainder derived will be the correct values of labdhi (y) and gu\d{n}a (x) respectively.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{\'{s}lokas from Bh{\=a}skar{\=a}charya's b{\=\i}jaga\d{n}itam}
i\d{s}\d{t}{\=a}hata\d{h} sva sva hare\d{n} yukto\\
te v{\=a} bhavet{\=a}\.m bahudh{\=a} gu\d{n}{\=a}pt{\=\i}\\
\vspace{0.5cm}
Multiply the divisor and dividend by any optional number and add them to the respective value of x and y and obtain many values of x and y. This is to find the general solution for x and y.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{An Example}
ekavi\.m\'{s}ati yuta\.m \'{s}atadvaya\.m\\
yad gu\d{n}a\.m ga\d{n}aka pa\~nca \d{s}a\d{s}\d{t}hi yuk\\
pa\~nca varjita \'{s}atadvayoddhruta\d{m}\\
\'{s}uddhimeti gu\d{n}aka\.m vada {\=a}\'{s}u tam\\
\vspace{0.5cm}
Which number (x) multiplied by 221 and increased by 65 is completely divisible by 195?\\
\vspace{0.5cm}
221x + 65 = 195y\\
\vspace{0.5cm}
13 is the GCD of 221, 65 and 195\\
\vspace{0.5cm}
Dividing by 13, we get\\
\vspace{0.5cm}
17x + 5 = 15y\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{An Example .. Contd}
17x + 5 = 15y\\
\vspace{0.5cm}
Dividend(bh{\=a}jya) = 17, Divisor(h{\=a}ra) = 15, k\d{s}epaka(constant) = 5\\
\begin{tabular}{|l|l|l|l|} \hline
Dividend & Divisor & Quotient & Remainder\\ \hline
17 & 15 & 1 & 2\\
15 & 2 & 7 & 1\\ \hline
\end{tabular}\\
\vspace{0.2cm}
\textbf{Valli}:\\
Place the quotients, constant and zero in a column.\\
\begin{tabular}{|l|} \hline
1\\
7\\
5\\
0\\ \hline
\end{tabular}
\vspace{0.2cm}
\begin{tabular}{||ll||} \hline
1& 1\\
7& 7*5+0=35\\
5& 5\\
0&\\ \hline
\end{tabular}
\vspace{0.2cm}
\begin{tabular}{|ll|} \hline
1& (35*1+5)=40\\
7& (7*5+0)=35\\
5& -\\
0&-\\ \hline
\end{tabular}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{An Example .. Contd}
17x + 5 = 15y\\
\vspace{0.2cm}
\begin{tabular}{|ll|} \hline
1& (35*1+5=) 40\\
7& (7*5+0=) 35\\
5& -\\
0&-\\ \hline
\end{tabular}\\
\vspace{0.2cm}
(35,40) is a possible solution.
Since (x+kn,y+kn) is a general solution, to get the smallest solution, we divide the values of y and x by dividend and divisor respectively such that the quotient is same. \\
40 / 17 : 40 = 17*2 + 6 ; y = 6\\
35 / 15 : 35 = 15*2 + 5 ; x = 5\\
\vspace{0.2cm}
Verification: 17x + 5 = 17 * 5 + 5 = 90 = 15 * 6 15y\\
\vspace{0.2cm}
General solution is $(15n + 5,17n + 6)$\\
\vspace{0.2cm}
Thus possible solutions are\\
(x,y) = (5,6), (20,23), (35,40),...
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Another Example}
Find all possible solutions of the equation\\
60x + 3 = 13y\\
\vspace{0.5cm}
Dividend = 60\\
Divisor = 13\\
Constant = 3\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Another Example .. contd}
\begin{tabular}{|llll|}\hline
Dividend & Divisor & Quotient & Remainder\\\hline
60 & 13 & 4 & 8\\
13 & 8 & 1 & 5\\
8 & 5 & 1 & 3\\
5 & 3 & 1 & 2\\
3 & 2 & 1 & 1\\\hline
\end{tabular}\\
\vspace{0.2cm}
Place the quotients, constant and zero in a column.\\
\begin{tabular}{l}
4\\
1\\
1\\
1\\
1\\
3\\
0\\
\end{tabular}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Another Example .. contd}
\begin{tabular}{ll} \hline
4 &  15*4+9 = 69\\
1 & 9*1+6  = 15\\
1 & 6*1+3 = 9\\
1 & 3*1+3 = 6\\
1 & 3*1+0 = 3\\
3\\
0\\ \hline
\end{tabular}\\
Since there are odd number of quotients, \\
y = 60 - 69 = -9\\
x = 13 - 15 = -2\\
So the solution is (-2,-9). \\
\vspace{0.2cm}
verification: 60 * -2 + 3 = -117 and 13 * -9 = -117\\
\vspace{0.2cm}
All possible solutions are\\
x = 13n-2, and y = 60n-9.\\
(-2,-9), (11,51), (24,111), ...\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Negative constant}
yogaje tatk\d{s}a\d{n}{\=a}t \'{s}ddhe\\
gu\d{n}{\=a}pti sto voyogaje\\
dhana bh{\=a}jyod bhave tad vad\\
bhavet{\=a}\.m \d{r}\d{n}a bh{\=a}jayo\\
\vspace{0.5cm}
The values of $x$ and $y$ obtained by reducing the results of ku\d{t}\d{t}aka with positive constant, should be subtracted from the divisor and dividend respectively for the solution of ku\d{t}\d{t}aka with negative constant.\\
\vspace{0.2cm}
If the solution of the equation $ax+c=by$ is $x = \alpha, y = \beta$,\\
then the solution of the equation $ax-c=by$ is $x = b-\alpha, y = a -\beta$\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Negative dividend}
Similarly if the dividend is negative, the result obtained with positive dividend should be subtracted from dividend and divisor to get the results.\\
\vspace{0.2cm}
Similarly, for the equation $-ax+c=by$, the solution will be $x = b-\alpha, y = \beta-a$, where $x = \alpha , y = \beta$ is the solution for $ax+c=by$.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Example}
The possible solutions of 60x+3 = 13y are (-2,-9), (11,51), .... \\
Or in general, x = 13n-2, and y = 60n-9.\\
\vspace{0.2cm}
What is the solution of 60x-3=13y?\\
\vspace{0.2cm}
Since the constant is negative, the solution will be\\
x = 13-11 = 2, and y = 60 - 51 = 9\\
In general the solution will be \\
x = 13n+2 and y = 60n+9.\\
The solutions are: (2,9), (15,69),...\\
\vspace{0.2cm}
What is the solution of -60x+3=13y?\\
\vspace{0.2cm}
Since the dividend is negative, the solution will be\\
x= 13-11 = 2, and y = -(60 - 51) = -9\\
\vspace{0.2cm}
What is the solution of -60x-3=13y?\\
Since the constant is negative, the solution will be\\
x = 13-2 = 11, and y = -60 -(-9) = -51
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Reduction factors}
bhavati ku\d{t}\d{t}vidhe\d{h} yuti bh{\=a}jyayo\d{h}\\
samapavartitayorapi v{\=a} gu\d{n}a\d{h}\\
bhavati yo yuti bh{\=a}jakayo\d{h} puna\d{h}\\
sa ca bhavet apavartana sa\.mgu\d{n}a\d{h}\\
\vspace{0.5cm}
If the constant and dividend of the ku\d{t}\d{t}aka are simplified by dividing with a common factor the value of the gu\d{n}a (x) obtained as solution of simplified ku\d{t}\d{t}aka will be correct but that of the labdhi(y) should be corrected by multipying with the reduction factor to give the solution of the original ku\d{t}\d{t}aka.\\
\vspace{0.5cm}
Similarly, if the constant term and divisor are reduced by dividing with a common reduction factor, the solution of the simplified ku\d{t}\d{t}aka will give the correct value of labdhi (y), but the gu\d{n}a (x) should be multiplied by the reduction factor to get the solution of the original ku\d{t}\d{t}aka.\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Reduction factor: explanation}
For example, consider the equation $ax+c = by$.\\
If $a$ and $c$ have a common factor, say, $k$.\\
Let $\frac{a}{k} = a_1$ and $\frac{c}{k} = c_1$.\\
Reduced ku\d{t}\d{t}aka is $a_{1}x + c_1 = by$.\\
Let the solution of this be $(\alpha,\beta)$.\\
Then the solution of $ax+c=by$ will be $(\alpha, k*\beta)$
\end{frame}
%============================================================%
\begin{frame}
Similarly, If $b$ and $c$ have a common factor, say, $k$.\\
\vspace{0.5cm}
Let $\frac{b}{k} = a_1$ and $\frac{c}{k} = c_1$.\\
Reduced ku\d{t}\d{t}aka is $ax + c_1 = b_1y$.\\
Let the solution of this be $(\alpha,\beta)$.\\
Then the solution of $ax+c=by$ will be $(k*\alpha, \beta)$
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Another Example}
yad gu\d{n}{\=a} k\d{s}ayaga \d{s}\d{s}\d{t}iravint{\=a}\\
varjit{\=a} ca yadi v{\=a} tr{\=i}bhi tata\d{h}\\
sy{\=a}t trayoda\'{s}a h\d{r}t{\=a} niragrak{\=a}\\
tam gu\d{n}am ga\d{n}aka me p\d{r}thak vada\\
\vspace{0.5cm}
Which number when multiplied by -60 and increased or decreased by 3 is divisible without remainder by 13. O, mathematician, please tell me the number.\\
\vspace{0.5cm}
The given equations are\\
-60x + 3 = 13 y\\
and -60x - 3 = 13y.\\
\vspace{0.5cm}
The dividend and the constant can be reduced by dividing by 3.\\
The redced equations are\\
-20x + 1 = 13y, and \\
-20x - 1 = 13y\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Reduction factors}
Let us solve 20x + 1 = 13y\\
\begin{tabular}{llll}\hline
Dividend & Divisor & Quotient & Remainder\\\hline
20 & 13 & 1 & 7\\
13 & 7 & 1 & 6\\
7 & 6 & 1 & 1\\\hline
\end{tabular}\\
\vspace{0.2cm}
Place the quotients, constant and zero in a column.\\
\begin{tabular}{|l|} \hline
1\\
1\\
1\\
1\\
0\\ \hline
\end{tabular}
\begin{tabular}{||ll||}\hline
1 &(1*2+1) = 3\\
1 &(1*1+1) = 2\\
1 &(1*1+0) = 1\\
1&1\\
0&-\\\hline
\end{tabular}\\
y = 3 and x = 2\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{ Example ... Contd}
Since the number of quotients is odd,\\
x = 13 - 2 = 11\\
y = 20 -3 = 17\\
So the solution for $20x + 1 = 13y$ is (11,17).\\
\vspace{0.5cm}
The solution for $-20x + 1 = 13y$, will be\\
x = 13-11 = 2, and y = -(20-17) = -3\\
\vspace{0.5cm}

Solution for $-60x+3=13y$ will be\\
x = 2, y = 3 * -3 = -9\\

Solution for $-60x-3=13y$ will be\\
x = 13-2 = 11 and y = -(60-(-9)) = -51
\end{frame}
%============================================================%
\begin{frame}
\frametitle{An example}
\'{s}atam hatam yena yutam navaty{\=a}\\
vivarjitam v{\=a} vih\d{r}tam tri\d{s}a\d{s}\d{t}y{\=a}\\
niragrakam sy{\=a}d vaxa me gu\d{n}am tam\\
sp\d{s}\d{t}a\.m pa\d{d}{\=\i}y{\=a}n yadi ku\d{t}\d{t}ake asi\\
\vspace{0.5cm}
Which number when multiplied with 100 and increased or reduced by 90 can be divided by 63 without remainder. If you are an expert in ku\d{t}\d{t}aka, please tell me that number.\\
\vspace{0.5cm}
The equation is: $100x+90 = 63y$\\
Reduce the dividend by 10 and divisor by 9\\
So the reduced equation is:\\
$10x+1=7y$\\
\begin{tabular}{|llll|} \hline
Dividend & Divisor & Quotient & Remainder\\
10 & 7 & 1 & 3\\
7 & 3 & 2 & 1\\ \hline
\end{tabular}\\
\vspace{0.2cm}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Solution ... contd}
Place the quotients, constant and zero in a column.\\
\begin{tabular}{|ll|} \hline
1 & (1*2+1) = 3\\
2 & (2*1+0) = 2\\
1 & 1\\
0 & -\\ \hline
\end{tabular}\\
So the solution of $10x + 1 = 7y$ is (x,y) = (2,3).\\
The solution of $100x+90=63y$ will be\\
x = 2*9 = 18; y = 3*10 = 30\\
So the general solution is (63n + 18, 100n + 30)\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Example ... Contd}
Solution of $100x-90=63y$ will be\\
x = 63 - 18 = 45, and\\
y = 100 - 30 = 70\\

So the general solution is (63n+45, 100n+70)\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Example}
a\d{s}\d{t}{\=a}da\'{s}a gu\d{n}{\=a}\d{h} kena da\'{s}{\=a}\d{d}hy{\=a} v{\=a} da\'{s}onit{\=a}\d{h}\\
\'{s}uddha\d{m} bh{\=a}ga\.m prayacchanti k\d{s}yagaik{\=a}da\'{s}oddh\d{r}t{\=a}\d{h}\\
\vspace{0.5cm}
Which number when multiplied by 18 and increased or reduced by 10 becomes completely divisible by -11?
\vspace{0.5cm}\\
The equations are $18x + 10 = -11y$ \& $18x - 10 = -11y$\\
Let us start with $18x+10 = 11y$\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Example ... Contd}
Let us start with $18x+10 = 11y$\\
\begin{tabular}{llll}\hline
Dividend & Divisor & Quotient & Remainder\\\hline
18 & 11 & 1 & 7\\
11 & 7 & 1 & 4\\
7 & 4 & 1 & 3\\
4 & 3 & 1 & 1\\\hline
\end{tabular}
\end{frame}
%============================================================%
\begin{frame}
Place the quotients, constant and zero in a column.\\
\begin{tabular}{|ll|}\hline
1 & 1*30+20 = 50\\
1 & 1*20+10 = 30\\
1 & (1*10+10) = 20\\
1 & (1*10+0) = 10\\
10 & 10\\
0 &-\\ \hline
\end{tabular}\\
Since there are even number of quotients,\\
y = 50 mod 18 = 14\\
x = 30 mod 11 = 8\\
So the solution for $18x+10=11y$ is (8,14)\\
Solution for $18x+10=-11y$ is (8,-14)\\
Solution for $18x-10=-11y$ is \\
x = -11-8 = -19  and y = 18-(-14) = 32\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Constant larger than divisor}
harata\d{s}\d{t}e dhanak\d{s}epa gu\d{n}a labdhitu p{\=u}rvavt\\
k\d{s}epa tak\d{s}a\d{n}a l{\=a}bh{\=a}dy{\=a} labdhi\d{h} \'{s}ddhau tu varjit{\=a}\\

\vspace{0.5cm}
If the constant $c$ is positive, and $c>b$, the constant $c$ can be reduced by dividing it by $b$ and using the remainder $c_1$ as the new constant. \\
Suppose the solution of the new equation $ax+c_1=by$ is ($x_1$,$y_1$), then the solution of $ax+c=by$ will be ($x_1$,$y_1+m$), where $m = \frac{c}{b}$.\\
If the constant is negative, the solution will be ($x_1$, $y_1-m$).

\end{frame}
%============================================================%
\begin{frame}
\frametitle{Constant larger than divisor}
athav{\=a} bh{\=a}h{\=a}re\d{n}a ta\d{s}\d{t}ayo\d{h} k\d{s}epabh{\=a}jyayo\d{h}\\
gu\d{n}a\d{h}A pr{\=a}gvat tato labdhi\d{h} bh{\=a}jy{\=a}ddhata yutoddh\d{r}t{\=a}t\\
\vspace{0.5cm}
An alternative method is: Divide both dividend and constant by the divisor and simplify. The value of $x$ will be correct. To get the value of $y$, multiply $x$ by $a$ and add $c$, divide the result by $b$.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Example}
yena samgun\d{n}it{\=a}\d{h} pa\~nca trayoovi\.m\'{s}ati sa\.yut{\=a}\d{h}\\
varjit{\=a} v{\=a} tribhi\d{h} bhakt{\=a} niragr{\=a}\d{h} syu\d{h} sa\d{h} ko gu\d{n}{\=a}\d{h}\\

\vspace{0.5cm}
Which number when multiplied by 5 and increased or reduced by 23 and divided by 3 leaves no remainder?\\
\vspace{0.5cm}
The equation is $5x+23=3y$\\
The constant (23) is larger than the divisor(3). So divide the constant 23 by 3, and take the remainder as new constant.\\
So the new equation is $5x+2=3y$\\

\begin{tabular}{llll}\hline
Dividend & Divisor & Quotient & Remainder\\\hline
5 & 3 & 1 & 2\\
3 & 2 & 1 & 1\\\hline
\end{tabular}

\end{frame}
%============================================================%
\begin{frame}
the quotients written in a column with constant and 0 \\
\begin{tabular}{ll} \hline
1 & (1*2+2) = 4\\
1 & (1*2+0) = 2\\
2 & 2\\
0 & -\\ \hline
\end{tabular}\\
The number of quotients is even.\\
So y = 4, x = 2\\
The solution of $5x + 23 = 3y$ is (2,4+7), where 7 = 23 div 3 \\
General solution is (2+3n, 11+5n).\\

The solution of $5x-23=3y$ is\\
x = 3 - 2 = 1, y = 5 - 11 = -6\\
So the general solution is (1+3n, -6+5n)\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Constant is Zero}
k\d{s}ep{\=a}bh{\=a}ve athav{\=a} yatra k\d{s}epa\d{h} \'{s}udheyd haroxdh\d{r}ta\d{h}\\
j~neya\d{h} \'{s}{\=u}nya\.m gu\d{n}a\d{h} tatra k\d{s}epo harah\d{r}ta\d{h} phala\.m\\

\vspace{0.5cm}
In the absence of numerical constant in the equation or when the constant is completely divisible by the divisor, the value of $x$ will be zero and the constant divided by the divisor will be the value of $y$.

In $ax+c=by$, if $c=0$, $ax=by$ \\
$\rightarrow$ $x=0$ (and $y=0$) is the solution\\
\vspace{0.5cm}
If $c$ is an integral multiple of $b$, (c=bn), then the general solution is\\
$y=n$ (and $x=0$).
\end{frame}
%============================================================%
\begin{frame}
\frametitle{An Example}
yena pa~nca gu\d{n}ita\d{h} kha sa\.myut{\=a}\d{h}\\
pa~nca \d{s}a\d{s}\d{t}i sahit{\=a}\d{h} ca te athav{\=a}\\
syu\d{h} trayoda\'{s}a h\d{r}t{\=a} niragrak{\=a}\\
tam gu\d{n}a\.m ga\d{n}aka k{\=\i}rtay{\=a}\'{s}u me\\

\vspace{0.5cm}

Which number, multiplied by 5 and combined with zero or increased by 65 is divisible by 13 without remainder? O Mathematician, please give me that number quickly.\\
\vspace{0.5cm}

The equation is $5x + 0 = 13y$ and $5x + 65 = 13y$\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{An Example ... Contd}
The equation is $5x + 0 = 13y$\\
When the constant is zero, $(x,y) = (0,0)$ is the solution\\
Hence general solution is:\\
x = 13m, y = 5m, m = 1,2,3,...\\
\vspace{0.5cm}
The equation is $5x + 65 = 13y$\\
13 is the common factor.\\
\vspace{0.2cm}
So the solution is:\\
$x=0, y=\frac{65}{13}=5$\\
\vspace{0.2cm}
General Solution is:\\
x = 13m, y = 5m + 5, m =1,2,3,..\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{sthira (invariant) ku\d{t}\d{t}aka}

k\d{s}epam vi\'{s}uddhi\.m parikalpya r{\=u}pa\.m\\
p\d{r}thak tayo\d{h} ye gu\d{n}ak{\=a}ra labdhi\\
abh{\=\i}psita k\d{s}epa vi\'{s}uddhi nighne\\
sva h{\=a}ra ta\d{s}\d{t}e bhavata\d{h} tayo\d{h} te\\

\vspace{0.5cm}
In a ku\d{t}\d{t}aka assuming constant $c$ to be equal to 1, find the value of $x$ and $y$. For an equation with the constant having the desired value (say $c$), multiply the values of $x$ and $y$ by this desired number. Reduce the results by dividing by $b$ and $a$ respectively and get the remainders as the values of $x$ and $y$.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Sthira ku\d{t}\d{t}aka: Example}
The solution for $8x+1=3y$ is $(x,y) = (1,3)$.\\
\vspace{0.5cm}
The solution for $8x+2=3y$ will be $(x,y) = (1*2,3*2) = (2,6)$\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Sthira ku\d{t}\d{t}aka:Proof}
Let the solution for $ax+1=by$ be $(x,y) = (\alpha,\beta)$.\\
\vspace{0.5cm}
Multiply this equation throughout by $c$. \\
We get $acx+c=bcy$. \\
Let $cx = x_1$ and $cy = y_1$.\\
\vspace{0.5cm}
So we get $ax_1 + c = by_1$, \\
where $(x_1,y_1) = (cx,yx) = (c*\alpha, c*\beta)$.\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Finding the smallest positive solution}

gu\d{n}a\d{h} labdhyo\d{h} samam gr{\=a}hya\.m\\
dh{\=\i}mat{\=a} tak\d{s}a\d{n}e phala\.m\\

\vspace{0.5cm}

While reducing the values of gu\d{n}a (x) and labdhi (y), by dividing with divisor, and dividend, an intelligent person should take the value of quotients to be equal. The values of $y$ and $x$ will be the remainders of such division.\\
\vspace{0.5cm}
This follows from the fact that the general solution is $(x+bn, y+an)$.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{An Example}

The solution of $8x+1=3y$ is $(x,y) = (1,3)$.\\
\vspace{0.5cm}
Hence the solution of $8x+11=3y$ would be $(x,y) = (11,33)$.\\
\vspace{0.5cm}
To get the smallest solution, divide $x$ and $y$ by a 3 and 8 respectively, such that the quotient is same. 
\vspace{0.5cm}
Thus we get $11/3 = 3+2/3; 33/8 = 3+9/8$. \\
So the above solution may be reduced to (2,9), as the smallest positive solution.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Mixed Kuttaka sa\.m\'{s}li\d{s}\d{t}a ku\d{t}\d{t}aka}
eko hara\d{h} ced gu\d{n}akau vibhinnau\\
tad{\=a} gu\d{n}aikya\d{m} parikalpya bh{\=a}jya\.m\\
agraikyamagram k\d{r}ta uktavadya\d{h}\\
sa\.m\'{s}li\d{s}\d{t}a samj~na\d{h} spu\d{t}aku\d{t}\d{t}aka\d{h} asau\\
\vspace{0.5cm}
In two ku\d{t}\d{t}akas, with common divisor, but different dividend and constants, the ku\d{t}\d{t}aka formed with the sum of dividends as new dividend and sum of constants as a new constant with the same divisor is called a mixed or conjunct ku\d{t}\d{t}aka.\\
\vspace{0.5cm}
For example, if $a_1 x+c_1=by$ and $a_2 x+c_2 = by$ are two ku\d{t}\d{t}akas, then\\
$(a_1+a_2)x + (c_1+c_2) = by$ is called the sa\.m\'{s}li\d{s}\d{t}a ku\d{t}\d{t}aka.\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Example}
ka\d{h} pa~ncanighno vih\d{r}ta\d{h} tri\d{s}a\d{s}\d{t}y{\=a}\\
sapta-ava\'{s}e\d{s}a\d{h} atha sa\d{h} eva r{\=a}\'{s}i\d{h}\\
da\'{s}{\=a}hata\d{h} sy{\=a}d vih\d{r}ta\d{h} tri\d{s}a\d{s}\d{t}y{\=a}\\
caturda\'{s}a agra\d{h} vada r{\=a}\'{s}imena\\

\vspace{0.5cm}
What is the number which when multiplied by 5 and divided by 63 leaves a remainder 7? and when multiplied by 10 and divided by 63 gives 14 as remainder? Please tell me the number.\\
\vspace{0.5cm}
The two equations are\\
$5x-7=63y$ and\\
$10x-14=63y$.\\
\vspace{0.5cm}
So the mixed ku\d{t}\d{t}aka is $15x-21=63y$.\\
On reduction, we get $5x-7=21y$.\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Example ... Contd}
Solution of $5x+7=21y$ is $(x,y) = (28,7) or (28 mod 21,7 mod 5) = (7,2)$.\\
Solution of $5x-7=21y$ will be $(x,y) = (21-7,5-2) = (14,3)$\\

Hence $x=14$ is the solution.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Quick Recap}
Aryabha\d{t}a's Algorithm for solving Linear Diophantine Equations\\
\begin{itemize}
\item Reduce the given equation to a simplified form removing the common factors(GCD).
\item Get the quotient of division of dividend and divisor. Repeat the process  with the divisor and the remainder till the remainder is 1.
\item Prepare a valli of quotients followed by the constant and 0.
\item multiply the penultimate term with the factor above and add the next term. Expunge the last term and repeat this process till you have only 2 values in the column.
\item If the number of quotients are even, these are the values of y and x modulo b and a respectively, if ax+c=by were the equation.
\item If the number of quotients are odd, then subtract these values from b and a respectively.
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Quick Recap .. Contd}
\begin{itemize}
\item If the solution of $ax+c=by$ is ($\alpha$,$\beta$)\\
then the solution of $ax-c=by$ is ($b-\alpha$,$a-\beta$)
\item If the solution of $ax+c=by$ is ($\alpha$,$\beta$)\\
then the solution of $-ax+c=by$ is ($-\alpha$,$\beta$), and\\
 the solution of $ax+c=-by$ is ($\alpha$,$-\beta$).
\item If in $ax+c=by$, $c>b$, and let $c=bm+c_1$, and\\
let the solution of $ax+c_1=by$ be ($\alpha$,$\beta$)\\
then the solution of $ax+c=by$ is ($\alpha$,$\beta+m$).
\item if $a=\frac{a_1}{k}$ and $c=\frac{c_1}{k}$, and the solution of
$a_1x-c_1=by$ is ($\alpha$,$\beta$), then the solution of
$ax-c=by$ is ($\alpha$,$k*\beta$).
\item if $b=\frac{b_1}{k}$ and $c=\frac{c_1}{k}$, and the solution of
$ax-c_1=b_1y$ is ($\alpha$,$\beta$), then the solution of
$ax-c=by$ is ($k*\alpha$,$\beta$).
\item If the solution of $ax + 1 = by$ is $(\alpha,\beta)$, then\\
the solution of $ax + c = by$ is $(c*\alpha,c*\beta)$.
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Proofs}
If the solution of $ax+c=by$ is ($\alpha$,$\beta$)\\
then show that the solution of $ax-c=by$ is ($b-\alpha$,$a-\beta$)\\
\vspace{0.5cm}
Proof: ($\alpha$,$\beta$) is the solution of $ax+c=by$.\\
Hence $a\alpha + c = b\beta$.\\
\vspace{0.5cm}
Subtracting each side from $ab$,\\
$ab - a\alpha - c = ab - b\beta$\\
$a(b-\alpha) -c = b(a-\beta)$\\
Hence the solution of $ax-c=by$ is ($b-\alpha$,$a-\beta$)\\
\end{frame}
%============================================================%
\begin{frame}
Exercise\\
\begin{itemize}
\item If ($\alpha$,$\beta$) is the solution of $ax+c=by$\\
prove that the solution of $-ax+c=by$ is ($-\alpha$,$\beta$), and\\
the solution of $ax+c=-by$ is ($\alpha$,$-\beta$).
\item If in $ax+c=by$, $c>b$, and let $c=bm+c_1$, and\\
let the solution of $ax+c_1=by$ be ($\alpha$,$\beta$)\\
then prove that the solution of $ax+c=by$ is ($\alpha$,$\beta+m$).
\item if $a=\frac{a_1}{k}$ and $c=\frac{c_1}{k}$, and the solution of
$a_1x-c_1=by$ is ($\alpha$,$\beta$), then prove that the solution of
$ax-c=by$ is ($\alpha$,$k*\beta$).
\item if $b=\frac{b_1}{k}$ and $c=\frac{c_1}{k}$, and the solution of
$ax-c_1=b_1y$ is ($\alpha$,$\beta$), then prove that the solution of
$ax-c=by$ is ($k*\alpha$,$\beta$).
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Simple equation}
Do you need a ku\d{t}\d{t}aka method to solve\\
\begin{center} $ax + c = y$ ? \end{center}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Intuition behind the Ku\d{t}\d{t}aka}
Example: $20x+1=13y$\\
\vspace{0.5cm}
Let $y = \frac{20x+1}{13} = x + \frac{7x+1}{13}$\\
\vspace{0.2cm}
For an integer solution of (x,y), $\frac{7x+1}{13}$ need to be an integer.\\
\vspace{0.5cm}
Let $z = \frac{7x+1}{13}$\\
So $x = \frac{13z-1}{7} = z + \frac{6z-1}{7}$\\
\vspace{0.2cm}
For an integer solution of (x,z), $\frac{6z-1}{7}$ need to be an integer.\\
\vspace{0.5cm}
Let $u = \frac{6z-1}{7}$\\
So $z =\frac{7u+1}{6} = u + \frac{u+1}{6}$\\
\vspace{0.2cm}
For an integer solution of (z,u), $\frac{u+1}{6}$ need to be an integer.\\
\vspace{0.5cm}
Let $t = \frac{u+1}{6}$\\
i.e., $6t = u+1$, whose integer solutions are $(t,u) = (n,6n-1), n=1,2,3,...$\\.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Intuition behind the Ku\d{t}\d{t}aka .. Contd}
Let us start with $t = 1$.\\
$u = 6t-1$. Hence $u = 5$.\\
$z = u + t$. Hence $z = 5 + 1 = 6$.\\
$x = z + u$. Hence $z = 6 + 5 = 11$.\\
$y = x + z$. Hence $y = 11 + 6 = 17$.\\
\vspace{0.2cm}
Hence the solution is (11,17).
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Ku\d{t}\d{t}aka: Continued Fractions}
The above solution may be represented as follows.\\
Example: $20x+1=13y$\\
$\frac{20}{13} = 1 + \frac{7}{13}$\\
\vspace{0.2cm}
$\frac{20}{13} = 1 + \frac{1}{\frac{13}{7}}$\\
\vspace{0.2cm}
$\frac{20}{13} = 1 + \frac{1}{1+\frac{6}{7}}$\\
\vspace{0.2cm}
$\frac{20}{13} = 1 + \frac{1}{1+\frac{1}{\frac{7}{6}}}$\\
\vspace{0.2cm}
$\frac{20}{13} = 1 + \frac{1}{1+\frac{1}{1+\frac{1}{6}}}$\\
\end{frame}
%============================================================%
\end{document}