Re: question regarding diofantine equations

In article <gerry-A5AC0B.14285711042007@xxxxxxxxxxxxxxxxxx>,
Gerry Myerson <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
In article <20070410.175730@xxxxxxxx>, rob@xxxxxxxxxxxxxx (Rob Johnson)
wrote:
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.

Although you could get lucky. E.g., pi x - y = sqrt 2 clearly has no
solutions in natural x, y - no canvassing required. pi x - y = pi - 1
clearly has the solution x = y = 1. pi x + y = e clearly has no
solutions in natural x, y. pi x - y = e is, I think, unknown.

Certainly, if c is given in the form of a solution, the search is very
short. Of course, even checking one possible answer, unless c is in
such a form, might be quite difficult. Situations can also be easily
vacated where one of a, b, and c is transcendental and the others are
algebraic, or one is irrational and the others are rational. But in
general, this is difficult.

However, I am curious why you claim that pi x + y = e has no solution
in natural x and y, but that it is unknown whether pi x - y = e has a
solution. It would seem that one has a solution if and only if the
other does.

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

Relevant Pages

  • Re: question regarding diofantine equations
    ... The algorithm is called the extended euclidean algorithm, ... element (equivalently, a/b is not rational). ... Gerry Myerson ...
    (sci.math)
  • Re: reducing large fractions
    ... > Is there some shortcut I'm missing? ... Yes, the Euclidean algorithm. ... Gerry Myerson ...
    (sci.math)
  • Re: reducing large fractions
    ... >> Could someone demonstrate the Euclidean algorithm using the fraction I ... > or roughly speaking, if there is no common factor), then ... Gerry Myerson ...
    (sci.math)
  • Re: question regarding diofantine equations
    ... Are there any methods for solving this? ... The algorithm is called the extended euclidean algorithm, ... element (equivalently, a/b is not rational). ...
    (sci.math)