Re: question regarding diofantine equations

In article <gerry-B2C6C7.08533011042007@xxxxxxxxxxxxxxxxxx>,
Gerry Myerson <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
In article <20070410.142106@xxxxxxxx>, rob@xxxxxxxxxxxxxx (Rob Johnson)
wrote:

In article <1176237012.557078.287790@xxxxxxxxxxxxxxxxxxxxxxxxxx>,
"laura" <laura.brandusan@xxxxxxxxx> wrote:
I want to solve diofantine equations of form:

ax+by=c,

where a, b and c are real numbers and

x and y are natural numbers (>=0).


Are there any methods for solving this ? I don't want to enumerate all
possible pairs (x,y) and to check which ones are good.

Or, is there possible to decide if the equation has solutions without
solving it?

The algorithm is called the extended euclidean algorithm, and one
implementation is the Euclid-Wallis Algorithm:

<http://www.whim.org/nebula/math/euclid-wallis.html>

OP wants a, b, and c to be real numbers. If b = 1 and c = 0
then the question of whether a x + b y = c has solutions is
the question of whether a is rational. It's going to take a heck of
an extension of Euclid's algorithm to decide whether, say, gamma
is rational.

Yes, I missed that a, b, and c were not necessarily integers.
With this generality, there are a couple of cases:

1. { ax + by : x,y are integers } has a smallest positive element, d
(equivalently, a/b is rational).

In this case, a/d and b/d are relatively prime integers, and the
equation has a solution if and only if c/d is an integer. Solutions
are given by the extended euclidean algorithm.

2. { ax + by : x,y are integers } does not have a smallest positive
element (equivalently, a/b is not rational).

Solutions here would require a canvassing of all values of x and y.

Rob Johnson <rob@xxxxxxxxxxxxxx>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
.

Relevant Pages