Solving Diophantine Equations
17feb11
1.1. 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.
2.2. The Solution
2.12.1. Some notation
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.
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.
2.22.2. The algorithm
We want to solve
Assuming that
else there is no solution.
Do a long-division step
If
then there is a trivial solution of (1) with
.
Else, we get an equivalent equation by substituting and rewriting.
|
where
is a just a renaming, which is invertible.
|
That is, if
is the solution to
then (6) yield
the solution to
.
2.32.3. The code
Jim Carlson's function
isolve(a,b,c) implements this algorithm recursively.
The variable
sol denotes the output of
isolve applied after
a long division step. The output is an ordered pair, the first element of which
is
sol[0] and the second element is
sol[1] . In mathematics,
we would not use a multiletter word for a vector
, and we would use
subscripts instead of the brackets.
2.42.4. An example
Here is a worked out
example