Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pells equation for D prime and =n*n-3

  1. Jul 18, 2012 #1
    I, retired physicist (working with high level radioactive waste regulation) and now amateur mathematician, have been looking at solutions for the Pell equation

    x*x-D*y*y=1, and I have in particular looked at the case D=n*n-3 which
    contains solutions with high values for x and y, such as for D=61.

    My simple studies have led me to formulate the following conjecture:

    When D in Pell’s equation x*x-D*y*y=1 is

    1) of the form n*n-3, and
    2) a prime number

    then

    x+1 contains a set of factors which

    a) includes D and
    b) includes one or more factors from y twice, i.e. in a squared form.

    For instance: x and y are the solution of x2-397y2=1 [x=838 721 786
    045 180 184 649, y= 42 094 239 791 738 438 433 660] and
    X+1 has the factors 2, 5^2, 17^2, 37^2, 173^2, 397, 1889^2, and

    y the factors 2^2, 3^3, 5, 17, 37, 173, 383, 1 889, 990 151, of
    which 5 appear as squares in x.

    My idea is that if z=x+1 and (z-1)*(z-1)-Dy=1, then z*z-2z-Dy=0 and it
    is possible to eliminate both D and more factors from the terms in the
    equation, thereby revealing simpler relations between smaller terms.

    (I also nourish a hope to find a general solution which will give me
    the lowest solution, in additions to the other techniques that are
    reported).

    Is this something that you can prove false, or is it correct, perhaps
    a well known fact?

    Thank you for any comments you might have.
     
  2. jcsd
  3. Jul 18, 2012 #2
    The example of x and y you gave doesn't work.
     
  4. Jul 18, 2012 #3
    It works only with the floor function it would seem...
    sqrt ((838721786045180184650^2 - 1)/397)
    = 4.2094239791738433660 050188561322849559546514506... × 10^19

    floor [sqrt ((838721786045180184650^2 - 1)/397)] = 42094239791738433660

    UPDATE: With help from Wolfram Alpha...

    x = ±1/2 (-(838721786045180184649-42094239791738433660 sqrt(397))^n-(838721786045180184649+42094239791738433660 sqrt(397))^n)
    y = ±((838721786045180184649-42094239791738433660 sqrt(397))^n-(838721786045180184649+42094239791738433660 sqrt(397))^n)/(2 sqrt(397)), n element Z, n>=0

    Closed form solutions for x and y, then, follow from simply substituting in integers for n.

    x follows the form...
    ±((-(a - b*sqrt(397))^n - (a + b*sqrt(397))^n))/2

    y follows the form...
    ±(((a - b*sqrt(397))^n - (a + b*sqrt(397))^n))/2*sqrt(397)

    a = 838721786045180184649
    b = 42094239791738433660

    397, obviously, = 20^2 - 3 = n*n - 3

    - AC
     
    Last edited: Jul 18, 2012
  5. Jul 18, 2012 #4
    I am not sure how to interprete the second comment, but perhaps I made an error with the very large numbers. I have not been able to copy and paste from Pari/gp.

    Try instead n=8, n*n-3=61 x = 1 766 319 049 and y = 226 153 980
    You will se the same pattern for x+1 (with 761 as the squared factor.)

    Or you can try with D= 10*10-3 97 , x=62 809 633, y=6 377 352 (with 569)

    or D=13 (with 5 a s the squared factor of x+1).
     
  6. Jul 18, 2012 #5
    Let me just add that I got the D=397 solution (and all the others) from Wolfram alpha. I then inserted x+1 into Pari using the function factor(x+1) and then compared with factor(y).
     
  7. Jul 18, 2012 #6
    The first post contains a typo, x=838 721 786 045 180 184 649 and y = 42 094 239 791 738 433 660 work. You included "438" (a mix of 738 and 433) in y by mistake. I got the correct values by multiplying out the factors in Mathematica. Interesting post, does it work for all solutions?
     
  8. Jul 18, 2012 #7
    In general, Mickey, I believe it would be helpful for you to frame n^2 - 3, as -- assuming n to be even -- (n-1)^2 + 4((n-2)/2). Thus, for example...

    (20-1)^2 + 4((20-2)/2) = 397
    (18-1)^2 + 4((18-2)/2) = 321

    Frame it that way and now you can insert into the Quadratic Formula:
    (18-1)^2 - 4(-(18-2)/2) --> b^2 - 4ac = Discriminant

    b = -(2ac + 1)

    - AC
     
    Last edited: Jul 18, 2012
  9. Jul 18, 2012 #8
    Also, Mickey, as a little mathematical factoid quite likely related to what you are doing... consider Lucas Sequences of U- and V- Type. One simple example is the Fibonacci Numbers (U) and the Lucas (V) Numbers. Another example is the Pell (U) Numbers and the Companion Pell (V) Numbers. A third example is the Mersenne (U) Numbers and the Fermat (V) Numbers.

    Since U_n*V_n = U_2n, it then becomes clear that all factors of V_n are also factors of U_n, but not vice versa.

    Lucas Sequence
    http://en.wikipedia.org/wiki/Lucas_sequence

    - AC
     
  10. Jul 19, 2012 #9
    Thank you all for your help.

    I don't think I can contribute to the statistics on high numbers to get data om high nn-3 primes. I suspect they get out of hand very soon. The results for D=397 were high enough. I might look a a few more using Wolfram alpha and Pari.

    The reason I started to look at Pell's equation was that I looked for primes
    p=4N+1=xx+yy, where xy divides 4N.

    For these x and y we can write xx+yy=2nxy+1 since one of xor y must be even.

    We can get a solution for x=ny+-sqrt((nn-1)y2+1) = ny+-z
    if zz-(nn-1)yy=1, i.e. Pell's equation for D=nn-1.

    This also connects to the Mersenne numbers 2^n-1 with a prime if for D=3
    (Using brahmagupta's methodfor the two first solutions) I got some xx+yy=2nxy+1 which I thought more often rendered primes for D=3 than for the non-primes nn-1 (n>2), but my statistics is really poor, since I was using excel, I got 5 solutions or 3 Brahmagupta iterations.

    I then saw that the third D below a square seems to give very high numbers.

    I have another question: Since a prime of the type nn-3 = 4n+1 is composed of two squares, I looked at some cases like this: xx-(aa+bb)yy=1
    It seems that a or b always (?) contain the factor 3.

    Is that obvious to you?
     
  11. Jul 20, 2012 #10
    I didn't have to work long on this problem to find that

    xx-Dyy=1 implies that

    xx-1=Dyy and therefore (x+1)(x-1)=Dyy

    so that x+1 must contain at least some factor f of y and therefore also ff of yy.

    What remains of my discovery is that D seems to be a factor of x+1 and not of x-1 at least for primes D=nn-3 (n=4, 8, 10,14, and 20) as far as I can see.

    If true, it leads to another Pell-like equation with a lower solution.

    yy-(nn-3)kk=-2k, k=(x+1)/(nn-3).
     
  12. Oct 3, 2012 #11
    Prof Hendrik from the Netherlands kindly provided me with the following proof for all d primes that x = -1 mod(d) (xx-dyy=1).

    "I first note that x is odd, since if x is even then y is
    odd, but now xx = 0 mod 4 and dyy + 1 = 2 mod 4, so that
    xx and dyy + 1 cannot be equal.

    So x is odd, and y must be even, say y = 2z. The two
    positive integers w = (x - 1)/2 and w + 1 = (x + 1)/2 are
    clearly coprime, and their product is d times a square. For
    d prime, this can only happen if one of them is a square, say
    uu, and the other is d times a square, say dvv. If w + 1
    is the one that is a square, then we get uu = w + 1 = dvv + 1.
    However, one has 0 < u < x, so this contradicts that x, y
    is the LEAST positive solution to the Pell equation. Hence it
    must be the other way around: w = uu, w + 1 = dvv, so that
    x + 1 = 2(w + 1) is indeed divisible by d."
     
  13. Oct 29, 2012 #12
    Let x(D) be a solution to Pell’s equation xx-Dyy=1 (x,y and D natural
    numbers).

    it seems few people are concerned with x as a function of D. Here is a conjecture along the lines toward such an understanding, or perhaps rather pattern recognition.

    If D is a prime = n(n+1)(n+2)+1 then

    • x(D) is increasing with D
    • x(D-1) is unusually low and x(D) is unusually high (NB the notorious case of D=61 is included), and
    • n is approximately proportional the logarithm of x(D), see table
    below.

    I realize there are a very limited number of cases presented, related to
    my own limitation of tools. I simply counted the digits from Wolfram
    Alpha's solutions. (Inclusion of non-primes would disturb the
    picture.)
    Observe that the 3 degree of the polynomial for D rules out a simple
    general polynomial representation of x, since the polynomial
    representing xx would have an odd degree.

    1st row: n / 2nd row: No of digits in x(D=n(n+1)(n+2)+1) / 3rd row: No of digits in x(D-1)

    1 1 1
    3 10 2
    5 12 2
    6 19 2
    9 29 3
    10 46 3
    13 51 3
    14 86 4
    18 133 5
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Pells equation for D prime and =n*n-3
  1. Pell's Equation (Replies: 4)

Loading...