Re: x^2 - Ay^2 =1

sttscitrans@xxxxxxxxx wrote :
On 19 May, 10:08, "Philippe 92" <nos...@xxxxxxxxxxxx> wrote:
...
sttscitr...@xxxxxxxxx wrote :
I suppose you could use the "Vincenzo method"
on a polynomial identity version of Pell's Equation
The f,g,h etc are polynimials with integer coefficients
f^2-gh^2 =1
...
The problem with polynomial Z[X] is worse as you can't define an
euclidian division :
you need Q[X], that is polynomial with _rational_ coefficients.

There does not have to be a Euclidean algorithm
on Z[sqrt(d)], but the continued fraction method
still works.

No, I speak about Z[X] that is the set of all polynomials in one
unknown X, with coefficients in integers Z.

[quote]
The f,g,h etc are polynimials with integer coefficients
[/quote]

You need to have some Euclidean _division_ to be able to get the
floor(sqrt(g)), that is find a polynomial which is the approximate
square root of polynomial g.
Inside the algorithm, you need also to use the Euclidean division to
get
a floor( some p/q ).

There just can't be any method of defining some Euclidean division of
polynomials in Z[X].
That is given a and b in Z[X] to find q and r in Z[X] with
a = b*q + r and 0 <= f(r) < f(b) with some indicator function f(p) for
any p in Z[X] -> f(p) in N, and some additional properties of f(), like
f(u*v) >= f(u) for any u,v != 0

The proof for that is quite easy.
Not imagine and try all possible functions f() ! but :
Suppose there were an Euclidean _division_, then it could be used to
define an Euclidean _algorithm_, which, extended, would lead to a
Bezout theorem : GCD(a,b) = a*u + b*v

Let a = X and b = 2, they are coprime that is GCD = 1, and it is
impossible to find u and v with X*u + 2*v = 1, just because the
constant term of X*u + 2*v is even, hence contradiction.

In Q[X], that is the set of polynomials with coeficients in Q
(rationals), such an Euclidean division exists, and f(p) is just the
degree of p.
For Euclidean division in integers, f() ist just the absolute value,
giving the usual 0 <= r < |b|

Hence many properties required to solve a Pell's like equation are no more
available.

Yes, you would think the cyclic method would work
on polynomoal Pell equations

How do you solve for p in a*p^2 + b*p + c = 0 with
a,b,c,p /in Z[X] ???

Regards.


--
Philippe C., mail : chephip+news@xxxxxxx
site : http://chephip.free.fr/ (recreational mathematics)


.

Relevant Pages

  • MACIS 2007 - CALL FOR PARTICIPATION
    ... Sciences (MACIS) is a new series of conferences where foundational research on theoretical and practical problems of mathematics for computing and information processing may be presented and discussed. ... Computing Roots of Polynomials using Bivariate Quadratic Clipping ... An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection ...
    (comp.specification.z)
  • Re: How to prove some inequality?
    ... where F and G are polynomials with positive integer coefficients. ... latter two expressions are expanded, with all the p's and q's somehow ...
    (sci.math)
  • Re: decomposition of polynomials
    ... but Googling "polynomial decomposition" will reveal ... problems for multivariate polynomials and for rational and algebraic ... O) algorithm for the decomposition of irreducible polynomials ... Technical Report TR87-826, Comput. ...
    (sci.math)
  • Re: once quasi asked about unions of sets ...
    ... multivariate, with integer coefficients, could have as its range ... the union of the set of multiples of 2 and the ... consider m-variate polynomials h with integer coefficients such that h ...
    (sci.math)
  • Re: euclidean algorithm over Q[i]
    ... Are you using the Euclidean algorithm to compute ... GCD's of univariate polynomials over Q? ... I'm not sure what 'pseudo division' may mean, ... Let b be the leading coefficient of G ...
    (sci.math.symbolic)
Loading