Solving Diophantine Equations
17feb11


\begin{document}
\maketitle


\section{Introduction}
In this lesson we study Jim Carlson's algorithm for solving a Diophantine
equation using Python and recursion. It is taken from the web document
 Jim Carlson 
"A Short Course in Python for Number Theory"  p11,12.

\section{The Solution}

\subsection{Some notation}
\textit{ Parentheses, brackets and braces.} \\
Parentheses in mathematics have many meanings, depending
on the context. But computers are not able to handle context. So
we must distinguish their use for grouping arithmetic expressions.
We can also leave them for writing functions because the name of 
the function preceeding their use establishes the functional context.
But for ordered pairs of numbers, we'll switch to square brackets.
Recall that is LaTeX braces take on very special grouping role. In 
some computer languages, braces take on a similar role.  

\textit{ The equals sign.} \\
In mathematics the equals sign always means an equation, which may
or may not be true. But it must be capable of being true or false.
We also use the equal sign when we substitute a single letter for 
a more complicated expression.  Sometimes, we use := for this purpose.  
But it is always correct to exchange right and left sides of an equation.
In computer languages the equals sign means quite something different,
and you may never exchange the sides here. The equal sign in Python 
as in other computer languates means that you assgn the value of the 
expression on the RHS to the object named on the LHS. 


\subsection{The algorithm}
We want to solve 
\begin{eqnarray*}  ax+by&=&c \mbox{    .......... (1) } \\ \end{eqnarray*}
Assuming that $gcd(a,b)|c$ else there is no solution. \\
Do a long-division step 
\begin{eqnarray*}  a&=&bq+r  \mbox{    .......... (2) } \\ \end{eqnarray*}
If $r=0$ then there is a trivial solution of (1) with $x=0, y=c/b$.

Else, we get an equivalent equation by substituting and rewriting. 
\begin{eqnarray*}  
(bq+r)x+by&=&c  \mbox{    .......... (3) } \\ 
b(qx+y)+r(x)&=&c  \mbox{    .......... (4) } \\ 
b(u)+r(v)&=&c  \mbox{    .......... (5) } \\ 
\end{eqnarray*}
where $[u,v]=[qx+y,x] $ is a just a renaming, which is invertible.
\begin{eqnarray*}  [x,y]&=&[v,u-qv]  \mbox{    .......... (6) } \\ \end{eqnarray*}

That is, if $[u,v]$ is the solution to $bu + rv=c$ then (6) yield
the solution to $ax+by=c$.

\subsection{The code}
Jim Carlson's function \texttt{ isolve(a,b,c)} implements this algorithm recursively.
The variable \texttt{sol} denotes the output of \texttt{ isolve } applied after
a long division step. The output is an ordered pair, the first element of which 
is \texttt{ sol[0] } and the second element is \texttt{ sol[1]}. In mathematics,
we would not use a multiletter word for a vector $s=[s_0,s_1]$, and we would use
subscripts instead of the brackets.  

\subsection{An example}
Here is a worked out  example 

\end{document}