Re: question regarding diofantine equations

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.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: question regarding diofantine equations
    ... Gerry Myerson wrote: ... The algorithm is called the extended euclidean algorithm, ... element (equivalently, a/b is not rational). ... pi x - y = e is, I think, unknown. ...
    (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)
  • 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: Simultaneous Linear Congruent Equations (solving)...
    ... understanding of how to apply the extended Euclidean Algorithm (I'll ... corresponding moduli product. ... Note that 11 appears in both lists. ...
    (sci.math)