Re: x^2 - Ay^2 =1

Vincenzo Librandi wrote :
For the Pell's equation:
x^2-Ay^2=1
If A=n^2+n (with n>0) then
y=8n+4 and x=8n^2+8n+1

...
To find the fundamental it is worth
a lot for all the method gcd.
...
(x odd number, x=/=0(mod 5)
search the fundamental:
...

Hi,

I'll answer about two points.

1) you could have found directly the fundamental solution for
all A = n^2 + n which are X = 2n+1, Y = 2
2) your "gcd method"


I'll name "property P" :=
"(X, Y) is a solution, and also U = X/GCD(X+1, Y), V = Y/GCD(X+1,Y)"

This property P is not true for all X,Y solution of any Pell's
equation (You are aware, and even insisted about X being odd etc...)
Obviously :

"if P, then X,Y is not a fundamental solution" is true
(just because there is then a solution U,V < X,Y)
but the point I insist on is :

If not P then ... we CAN'T SAY ANYTHING about X,Y being fundamental
or not. This is a problem of logic, not of Pell's equation.

Now let's precise this property P a little more.

Let g _any_ common divisor of X+1, Y
that is X+1 = g*u, and Y = g*v
X,Y being a solution (g*u - 1)^2 - A*(g*v)^2 = 1
that is g^2*u^2 - A*g^2*v^2 = 2*g*u

u, v will be a solution if and only if 2*u/g = 1, that is g = 2*u
u, v being then coprime ( GCD(u^2,v^2) divides 1 ), g = GCD(X+1,Y)


This implies : for property P to be true, X+1 must be = 2*u^2
that is X+1 even and X+1 = 2*{0,1,4,4,1} = {0,2,3} mod(5)
that is X = {4,1,2} mod(5) that is X not = 0 or 3 mod(5)

There is then a condition you missed : X =/= 3 mod(5)

But this is not a complete condition, there are odd X with
X =/= {0, 3} mod(5) wich are not 2*u^2 - 1.
The real condition for the 'gcd' method to be worth being tried is

**********************************
* X+1 is the double of a square *
**********************************

If not, just property P can't be true.

This is not a sufficient condition. There are solutions with
X+1 being the double of a square, for which property P is false,
and X is not the fundamental solution.

I allready gave an example, with quite big values.
Knowing now the exact condition, I give a new lower example :
A = 12, X = 1351, Y = 390
X odd, X = 1 mod 5
X+1 = 2*26^2
GCD(X+1,Y)=26
u = (X+1)/GCD = 52, v = Y/GCD = 15
u^2 - 12v^2 = 4
The conditions for applying the GCD method are satisfied
(X+1 double of a square) and property P is false (u, v not a
solution) but 1351,390 is not the fundamental solution (7,2).


Now suppose X,Y is just the second solution, naming X0, Y0
the fundamental solution. That is all the sorted solutions are
(1,0), (X0,Y0), (X,Y), [then other greater solutions]...
Hence X = 2*X0*X0 - 1, Y = 2*X0*Y0 - 0 (usual recurrence relations)
X+1 is then the double of a square and property P is then
satisfied for X,Y (and gives X0, Y0)

***************************************************************
* For all X,Y of which WE KNOW they are the second solution, *
* the 'gcd algorithm' gives the fundamental one. *
***************************************************************

But usually we don't know in advance that X,Y is precisely the
second solution...
And as not P doesn't implies that X,Y is fundamental, Again I repeat
the 'gcd method' is not a RELIABLE method to find the fundamental.
(because it may say erroneously a not fundamental is a fondamental)

All the solutions you've found are from polynomials, which when
not giving the fundamental, give the second solution.
Hence all solutions you have tried comfort you in believing in the
"gcd method". You should not. But instead find polynomials which
directly give the fundamental, and prooving this is the fundamental.
I gave an example in some previous post.
Here you got :

If A=n^2+n (with n>0) then
y=8n+4 and x=8n^2+8n+1

Even applying your gcd method : x+1 = 8n^2+8n+2 = 2(2n+1)^2
x+1 being the double of a square, the gcd method is worth the effort.
y = 4*(2n+1) hence multiple of 2*(2n+1) which is a common divisor.
dividing by 2*(2n+1), you get X = 2n+1, Y = 2, X,Y coprime (X odd)
This is then a solution, and it is fundamental as any lower solution
would be y = 1, then x^2 = 1 + (n^2+n)*1^2 = n^2 + n + 1, n>0, is
not a square (you have to proove it is _never_ a square, not hard).
Hence there is no lower solution.

********************************************************
* The fundamental solution of x^2 - A*y^2, A=n^2+n is *
* X = 2n+1, Y = 2 *
********************************************************

You should do the same thing on your other polynomials before
posting them (the list of numeric values is useless).

Regards.

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


.

Relevant Pages
Quantcast