1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Newton (iterative) method to solve a diophantine equation

  1. Nov 2, 2006 #1
    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:
  2. jcsd
  3. Nov 2, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Nov 10, 2006 #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:

    "..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: Nov 10, 2006
  5. Nov 12, 2006 #4
    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.
  6. Nov 22, 2006 #5
    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
  7. Nov 23, 2006 #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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Newton (iterative) method to solve a diophantine equation
  1. A diophantine equation (Replies: 8)

  2. Diophantine equations (Replies: 3)

  3. Diophantine Equation (Replies: 1)

  4. Diophantine equation (Replies: 3)