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: [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: May 2, 2017
  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.
    Last edited by a moderator: May 2, 2017
  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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook