Newton (iterative) method to solve a diophantine equation

[Karlisbad]

My question is..how could we use Newton method (or other iterative method ) to solve:

Nx^2 -y^2=1 ?? :confused: :confused:

The main problem i see is that the equation before could have some "non-integer" solutions note that (1) can be put in the form:

\sqrt(Nx^2 -1)=y :grumpy:

[matt grime]

Jose, or whatever psuedonym they force you to post under these days, please, can I ask you to just think for *one second* before posting asinine garbage like this? There exist *uncountably* many soultions to this problem. Numerical solutions cannot distinguish between the integer and non-integer solutions. The classical (hundreds of years old) theory of binary quadratic forms might be of interest. It is a subject that every mathematician has forgotten more about than you will ever learn.

[robert Ihnot]

The equation in integers X^2-NY^2=+/- 1 is known as the Pell's Equation which had little to do with Pell, but was first understood by Fermat.

A solution to X^2-NY^2=-1 is possible when N is composed of primes congruent to 1 Modulo 4. However, it is also true for N=2. (Thus a solution can be found for N=5, 2^2-5*1^2=-1.) If one solution can be found, in general there are an infinite number of solutions.

The exact answer for cases to the -1 where 2^n is a factor of N is rather tricky and I note from Wolfram. http://mathworld.wolfram.com/PellEquation.html:

"..and that cannot be doubly even (i.e., divisible by 4).
However, (the above) conditions are not sufficient for a solution to exist, as demonstrated by the equation , X^2-34Y^2=-1 which has no solutions in integers (Nagell 1951, pp. 201 and 204)."

However, the equation X^2-20Y^2=1 is satisifed by X=9, Y=2. This comes about because if we have a solution to X^2-NY^2=-1. Then we can "look down the road" and look at this equation:

(X^2+NY^2)^2-N(2XY)^2 which when expanding and collecting terms reduces to X^4-2N(XY)^2 +N^2Y^4=(X^2-NY^2)^2 =(-1)^2=1.

But the term -N(2XY)^2 =-4N(XY)^2 so that we have an N that has been multipled by 4, however we are solving for the plus 1.

[robert Ihnot]

The equation in integers X^2-NY^2=+/- 1 is known as the Pell's Equation which had little to do with Pell, but was first understood by Fermat.

A solution to X^2-NY^2=-1 is possible when N is composed of primes congruent to 1 Modulo 4. However, it is also true for N=2. (Thus a solution can be found for N=5, 2^2-5*1^2=-1.) If one solution can be found, in general there are an infinite number of solutions.

The exact answer for cases to the -1 where 2^n is a factor of N is rather tricky and I note from Wolfram. http://mathworld.wolfram.com/PellEquation.html:

"..and that cannot be doubly even (i.e., divisible by 4).
However, (the above) conditions are not sufficient for a solution to exist, as demonstrated by the equation , X^2-34Y^2=-1 which has no solutions in integers (Nagell 1951, pp. 201 and 204)."

However, the equation X^2-20Y^2=1 is satisifed by X=9, Y=2. This comes about because if we have a solution to X^2-NY^2=-1. Then we can "look down the road" and look at this equation:

(X^2+NY^2)^2-N(2XY)^2 which when expanding and collecting terms reduces to X^4-2N(XY)^2 +N^2Y^4=(X^2-NY^2)^2 =(-1)^2=1.

But the term -N(2XY)^2 =-4N(XY)^2 so that we have an N that has been multipled by 4, however we are solving for the plus 1.

Also if X^2-4pY^2=-1, then X^2==-1 (Mod 4), but this is not possible for even squares and all odd squares are congruent to 1 mod 4 and mod 8.

[Playdo]

My question is..how could we use Newton method (or other iterative method ) to solve:

Nx^2 -y^2=1 ?? :confused: :confused:

The main problem i see is that the equation before could have some "non-integer" solutions note that (1) can be put in the form:

\sqrt(Nx^2 -1)=y :grumpy:

Taking your approach Karlisbad, suppose N is a perfect sqaure say N = M^2 then

y^2 = (Mx-1)(Mx+1)

Since Mx-1 and Mx+1 are coprime each must be a perfect square to satisfy the equation that of course is impossible since their difference is 2 whereas the difference of any two consecutive squares is greater than that (2x+1)

Consider, let M be the largest square integer less than N, and K^2 = M.

y^2+1 = Nx^2

This is the same thing as saying

y^2+1 = \sum_{i=1}^{N}x^2

Parametrize y as y = x + k

(x+k)^2+1 = = k^2x^2 + 2xk + k^2 +1= \sum_{i=1}^{N}x^2

Suppose N > k^2 we have

(N-k^2)x^2 - 2xk -k^2-1 = 0

Nx^2 - k^2x^2 = k^2 + 2xk + 1

Let x = 1 and we get

N - k^2 = (k+1)^2

N = (k+1)^2 + k^2

A very long way to say that if x = 1 then you are looking for

y^2+1 = N, but for any integer y you can easily find N.

Let x = 2 and you get y^2 = 4N-1

NO solutions because 3*3 =1 mod 4

Let x = 3 you get y^2 = 9N-1

So do this

(sx^2+r)^2 = x^2N-1

s^2x^4 + 2rsx^2+r^2 = Nx^2-1

r^2 = -1 mod x^2

which means that x^2-1 is a perfect square which is false for x>1. It expects this x^2-1 = t^2 , (x+t)(x-t)=1 in integers that is only satisfied buy x =1, t=0

[robert Ihnot]

Playdo: Taking your approach Karlisbad, suppose N is a perfect sqaure say N = M^2 then

If N was a perfect square we would have the form u^2-v^2 =1. Giving the trivial solution u=1, v=0.