Newton (iterative) method to solve a diophantine equation

In summary: This would be the same as stating N=2, which would mean that the equation is not solvable. So obviously we are looking for non-perfect squares.In summary, the conversation discusses the use of Newton's method or other iterative methods to solve the equation Nx^2 - y^2 = 1. It also presents the problem of finding non-integer solutions and provides some possible solutions through the use of parametrization and equations involving perfect squares. The conversation also mentions the classical theory of binary quadratic forms and provides some background information on the Pell's equation.
  • #1
Karlisbad
131
0
My question is..how could we use Newton method (or other iterative method ) to solve:

[tex] Nx^2 -y^2=1 [/tex] ?? :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:

[tex] \sqrt(Nx^2 -1)=y [/tex] :grumpy:
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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: [Broken]

"..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.
 
Last edited by a moderator:
  • #4
robert Ihnot said:
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: [Broken]

"..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.
 
Last edited by a moderator:
  • #5
Karlisbad said:
My question is..how could we use Newton method (or other iterative method ) to solve:

[tex] Nx^2 -y^2=1 [/tex] ?? :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:

[tex] \sqrt(Nx^2 -1)=y [/tex] :grumpy:

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

[tex] y^2 = (Mx-1)(Mx+1)[/tex]

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.

[tex] y^2+1 = Nx^2 [/tex]

This is the same thing as saying

[tex] y^2+1 = \sum_{i=1}^{N}x^2 [/tex]

Parametrize y as y = x + k

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

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
 
  • #6
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.
 

1. What is the Newton (iterative) method to solve a diophantine equation?

The Newton (iterative) method is a numerical method used to find approximate solutions to equations that cannot be solved algebraically, such as diophantine equations. It involves using an initial guess for the solution and then continuously refining that guess through a series of iterations until a close enough solution is found.

2. How does the Newton (iterative) method work?

The method works by starting with an initial guess for the solution and then using the derivative of the equation to determine the slope of the curve at that point. This slope is used to find the next approximation for the solution, which is then used to find the new slope. This process is repeated until the solution is within a desired level of accuracy.

3. What types of equations can the Newton (iterative) method be used to solve?

The Newton (iterative) method can be used to solve a wide range of equations, including diophantine equations, transcendental equations, and polynomial equations. However, it is most commonly used for equations that cannot be solved algebraically.

4. What are the advantages of using the Newton (iterative) method to solve a diophantine equation?

One of the main advantages of using the Newton (iterative) method to solve a diophantine equation is that it can provide a very accurate solution, often with just a few iterations. It is also a relatively simple and straightforward method to implement, making it a popular choice among mathematicians and scientists.

5. Are there any limitations to the Newton (iterative) method?

Yes, there are some limitations to the Newton (iterative) method. One limitation is that it may not always converge to a solution, especially for equations with multiple solutions or complex solutions. Additionally, the method may require a large number of iterations to find a solution for certain equations, making it computationally intensive. Finally, the method may not work well for equations with discontinuous or undefined derivatives.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
583
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
866
Replies
1
Views
10K
  • Programming and Computer Science
Replies
4
Views
498
  • Precalculus Mathematics Homework Help
Replies
3
Views
3K
Replies
4
Views
668
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Replies
16
Views
1K
Back
Top