Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Pell-like Diophantine Equations

Date: 10/05/2010 at 10:40:18
From: Colin
Subject: Find a solution to a Pell-like Diophantine equation

Given

      o = 1/5*2^(-t)*((5 - 2*5^(1/2))*(3 - 5^(1/2))^t 
                    + (3 + 5^(1/2))^t*(5 + 2*5^(1/2)))

   f(o) = 59000294016949115852899 + 79385788658193619291515*o^2

   f(t) = y^2

Solve for t and y (in whole numbers).

I know there are formulas to calculate f(o). And thanks to the Ask Dr.
Math website, I can solve Pell (quadratic), cubic, and some quartic
equations. But the t as an exponent variable of o confuses me.

When I tried integer values for t, I was surprised to find that o always
came out as a whole number (?!). Examples are:

   t =  1, o =     5       f(t) =        2043645010471789598140774
   t =  2, o =    13       f(t) =       13475198577251670776118934
   t =  3, o =    34       f(t) =       91828971982888773016844239
   t =  4, o =    89       f(t) =      628873832255568607523943214
   t =  5, o =   233       f(t) =     4309834080758690346832910734
   t =  6, o =   610       f(t) =    29539510960007862687488584399
   t =  7, o =  1597       f(t) =   202466288866248947332769332534
   t =  8, o =  4181       f(t) =  1387724057330687367509078895814
   t =  9, o = 10946       f(t) =  9511601658675515224097965090639
   t = 10, o = 28657       f(t) = 65193487099624871800043858891134

Very interesting. However, where to go from here?

The only way I know to do this is by brute force, checking whether f(t) is
a perfect square for a lot of t values. However, there must be a more
strategic way to do this.

Unfortunately, working with powers, square roots, and perfect squares is
way beyond the math I currently use.

These equations seem very difficult.



Date: 10/06/2010 at 14:56:50
From: Colin
Subject: Find a solution to a Pell-like Diophantine equation

After some calculations, I managed to simplify the expression. Using plain
text convertible to any software package:

   2^(-2*t)*(59000294016949115852899*2^(2*t)
           + 142894419584748514724727*(3 - 5^(1/2))^(2*t)
           - 63508630926554895433212*5^(1/2)* (3 - 5^(1/2))^(2*t)
           + 142894419584748514724727*(3 + 5^(1/2))^(2*t) 
           + 63508630926554895433212*5^(1/2)*(3 + 5^(1/2))^(2*t) 
           + 31754315463277447716606*((3 - 5^(1/2))*(3 + 5^(1/2)))^t)

Since I am looking for a perfect square, I can leave out 2^(-2*t), which
is equal to 1/(2^2t) and always a square. Removing this part, the
expression becomes

             59000294016949115852899*2^(2*t)
           + 142894419584748514724727*(3 - 5^(1/2))^(2*t) 
           - 63508630926554895433212*5^(1/2)* (3 - 5^(1/2))^(2*t)
           + 142894419584748514724727*(3 + 5^(1/2))^(2*t)
           + 635086309265 54895433212*5^(1/2)*(3 + 5^(1/2))^(2*t)
           + 31754315463277447716606*((3 - 5^(1/2))*(3 + 5^(1/2)))^t

I used my software package to simplify it even further:

             90754609480226563569505*4^t 
           - 15877157731638723858303*(3 - 5^(1/2))^(2*t)*(-9 + 4*5^(1/2))
           + 15877157731638723858303*(3 + 5^(1/2))^(2*t)*(9 + 4*5^(1/2))

When working with the software, this seems to be a reasonable expression.
But how do you find a perfect square?

The next thing I did was make the (wrong!) assumption that these terms
should be zero:

             15877157731638723858303*(3 - 5^(1/2))^(2*t)*(-9 + 4*5^(1/2)) 
           + 15877157731638723858303*(3 + 5^(1/2))^(2*t)*(9 + 4*5^(1/2))

However, when dividing this part by the same formula with t = t - 1 (to
measure the growth), there seems to be some kind of near constant
involved. I used the following formula:

      (15877157731638723858303*(3 - 5^(1/2))^(2*t)*(-9 + 4*5^(1/2)) 
     + 15877157731638723858303*(3 + 5^(1/2))^(2*t)*(9 + 4*5^(1/2)))
     /(15877157731638723858303*(3 - 5^(1/2))^(2*(t - 1))*(-9 + 4*5^(1/2)) 
     + 15877157731638723858303*(3 + 5^(1/2))^(2(t - 1))*(9 + 4*5^(1/2)))

Again, my software optimized this into

     (8*((3 - 5^(1/2))^(2*t)*(- 9 + 4*5^(1/2)) 
       + (3 + 5^(1/2))^(2*t)*(9 + 4*5^(1/2))))
       /(-(3 - 5^(1/2))^(1 + 2*t)
       + (3 + 5^(1/2))^(1 + 2*t))

Next, I worked out these answers for t:

   t =  1, answer = 55/2
   t =  2, answer = 1508/55
   t =  3, answer = 10336/377
   t =  4, answer = 17711/646
   t =  5, answer = 485572/17711
   t =  6, answer = 3328160/121393
   t =  7, answer = 5702887/208010
   t =  8, answer = 156352676/5702887
   t =  9, answer = 1071657184/39088169
   t = 10, answer = 1836311903/66978574

This seems like a random formula, but when I leave the Diophantine
calculations for a moment and try to convert these fractions to real
numbers, the following happens:

  t =  1, answer = 55/2                =  27.5
  t =  2, answer = 1508/55             =  27.4181818181818181818181818182
  t =  3, answer = 10336/377           =  27.4164456233421750663129973475
  t =  4, answer = 17711/646           =  27.4164456233421750663129973475
  t =  5, answer = 485572/17711        =  27.4164078821071650386765287110
  t =  6, answer = 3328160/121393      =  27.4164078653629121942780885224
  t =  7, answer = 5702887/208010      =  27.4164078650064900725926638142
  t =  8, answer = 156352676/5702887   =  27.4164078649989031871050574911
  t =  9, answer = 1071657184/39088169 =  27.4164078649987416908681498998
  t = 10, answer = 1836311903/66978574 =  27.4164078649987382532210972422

  ...

  t = 44, answer = 194234116577741760478883222676916790564
                   /7084593923980518516849609894969925639

                                       =  27.4164078649987381784550420124

   ...

  t = 200, answer = 49729378389375189748513097521548297905221664813821729
                    49995036319462386077730344349197286340438682643217344
                    98566048534612944607947514664925153955810899369903146
                    58228041321813854631658817368902122088853366253063423
                    74187644712456957150207333853274302654579519133876533
                    53160380734487341694569815399019123399954517515126184
                    5669004727753362151

                                       =  27.4164078649987381784550420124

The last numbers, with 30 digits behind the decimal point, are (near)
equal. Expanded to a hundred decimals, however, reveals

  t = 44,  answer = 27.41640786499873817845504201238765741264371015766915
                    434562538347246312555393375121072780862059986048

  t = 200, answer = 27.41640786499873817845504201238765741264371015766915
                    434562538347246312555382682939648648645027269365

My conclusion from these numbers is that it is very strange that a (part
of this) formula with a lot of square roots and a power variable can be
approximated this easily. At first I thought finding a perfect square
would be impossible, but from the last calculations this may not be true!

Now let's use the whole thing and check for growth:

             90754609480226563569505*4^t
           - 15877157731638723858303*(3 - 5^(1/2))^(2*t)*(-9 + 4*5^(1/2))
           + 15877157731638723858303*(3 + 5^(1/2))^(2*t)*(9 + 4*5^(1/2))

It is easy to see that the difference between f(t) and f(t - 1) will
eventually be 4 as t reaches infinity, since this is 

   4^t/4^(t - 1) == 4

However, I cannot say more about finding a perfect square in general,
since this requires more knowledge of advanced math than I have.

My software package starts to complain about non-algebraic solutions when
I try to calculate a formula that generates perfect squares for t, so that
must be why I'm having difficulties solving it.



Date: 10/07/2010 at 00:49:00
From: Doctor Vogler
Subject: Re: Find a solution to a Pell-like Diophantine equation

Hi Colin,

Thanks for writing to Dr Math. That's an interesting question. First of
all, if you've studied Pell-like Diophantine equations, then you may
recognize recurrences like the following: your function o(t) has the 
form ...

   o(t) = A*r^t + B*s^t

... where r and s are the numbers

   (3 + sqrt(5))/2  and  (3 - sqrt(5))/2.

Those are the roots of the polynomial x^2 - 3x + 1 = 0.

                x = (3 + sqrt(5))/2
               2x = 3 + sqrt(5)
           2x - 3 = sqrt(5)
       (2x - 3)^2 = 5
   4x^2 - 12x + 9 = 5
   4x^2 - 12x + 4 = 0
     x^2 - 3x + 1 = 0.

Powers of roots of polynomials relate to recurrence relations in that the
general solution to the recurrence relation ...

   o(t + 2) - 3*o(t + 1) + o(t) = 0

... is ...

   o(t) = A*r^t + B*s^t

... for those values of r and s. You should also check directly that your
formula for o(t) satisfies the recurrence

   o(t + 2) = 3*o(t + 1) - o(t).

That equation, together with the initial conditions o(1) = 5, o(2) = 13,
makes it obvious that o(t) has to be an integer for every positive 
integer t.

Now, you want to find integers y and t such that

   y^2 = 59000294016949115852899 + 79385788658193619291515*o(t)^2.

If the o could just be any integer, then you would have a Pell equation.
But you have a specific formula for o(t).

Consider this: you start with o(1) = 5 and o(2) = 13, which are both 
1 mod 4; that is, if you divide either one by 4, you get a remainder of 1.
But then when you use the recurrence ...

   o(t + 2) = 3*o(t + 1) - o(t),

... you get ...

   o(3) = 2 mod 4
   o(4) = 1 mod 4
   o(5) = 1 mod 4
   o(6) = 2 mod 4
   
... and so on, repeating 1, 1, 2, 1, 1, 2, 1, 1, 2, ad infinitum. Then
when you compute ...

   59000294016949115852899 + 79385788658193619291515*o(t)^2, -1 + -1{2,3}

... this number is 

   2 mod 4 when o is 1 mod 4
   3 mod 4 when o is 2 mod 4
   
But a square is always either 0 mod 4 or 1 mod 4 -- never 2 or 3 mod 4. So
you can never have

   y^2 = 59000294016949115852899 + 79385788658193619291515*o(t)^2.

There are no solutions with y and t both positive integers.

If you have any questions about this or need more help, please write back
and show me what you have been able to do, and I will try to offer further
suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 10/07/2010 at 05:04:33
From: Colin
Subject: Find a solution to a Pell-like Diophantine equation

Thank you very much for your simple answer. I completely missed the square
root part.

However, since your answer is so simple and since I've managed to simplify
the equation to one that's not so intimidating, my main question remains.
Namely, what would be a good method to solve this equation if it were
solvable?

Is there another method besides determining whether it is solvable at all?

Let's say that this ...

   y^2 = 59000294016949115852899 + 79385788658193619291515*o(t)^2

... becomes this:

   y^2 = 59000294016949115852899 - 1 + 79385788658193619291515*o(t)^2

I am not asking for a full calculation -- although it would be nice. I'm
asking for a method to solve this type of equations. I'm very interested
in the advanced (at least to me) math involved in working with these
Diophantine equations.



Date: 10/07/2010 at 09:18:00
From: Colin
Subject: Find a solution to a Pell-like Diophantine equation

First of all, thanks for your detailed answer.

I would like to add that you should ignore my previous post; I completely
overlooked the part about testing square roots. In my previous post, a
square root part is possible for mod 4. But what if one tests with other
numbers?

To my knowledge, this equation never generates a square root (3 mod 7):

   y^2 = 59000294016949115852899 - 1 + 79385788658193619291515*o(t)^2 

So subtracting one was not very smart of me. Instead, I modified the
formulas to this:

   o = 1/5*2^(-t)*((5 - 2*5^(1/2))*(3 - 5^(1/2))^t
                 + (3 + 5^(1/2))^t*(5 + 2*5^(1/2)))
                 
   f = 59000294016949115852899 + 79385788658193619291515*o^2 
       + 1536863916975701607562634398127852011969795266

I added 1536863916975701607562634398127852011969795266 to f, because that
gives my formula at least one solution. That is what I want, since I am
interested in the math behind solving this formula:

   f(t) = y^2

Now with this modified formula, it is possible to find a solution:

   t = 10, y = 39202855979836045626920.
   
So, now back to my original question: how can I find this answer in a
mathematical way?

Are there other solutions?

I know that calculating all values for t between 1 and 100 is easy to do
and also gives an answer. But what if there were an extremely large t (or
multiple); would it be possible to calculate these values without
sequentially trying values for t?



Date: 10/08/2010 at 02:37:04
From: Doctor Vogler
Subject: Re: Find a solution to a Pell-like Diophantine equation

Hi Colin,

Thanks for writing to Dr. Math. That's a good question. But what a
complicated equation to learn a new technique!

Your original problem is this: if you set ...

   r = (3 + sqrt(5))/2
   s = (3 - sqrt(5))/2
   A = (5 + 2*sqrt(5))/5
   B = (5 - 2*sqrt(5))/5
   C = 59000294016949115852899
   D = 79385788658193619291515

... then you want integer (t, y) solutions to the equation

   y^2 = C + D*(A*r^t + B*s^t)^2.

Your new problem is the same, except with

   C = 59000294016949115852899 
       + 1536863916975701607562634398127852011969795266

Now, the square on the right is actually not very important to the form of
the equation, since rs = 1. So ...

   y^2 = C + D*(A^2*r^(2t) + 2*A*B + B^2*s^(2t))

   y^2 = (C + 2*A*B*D) + (D*A^2)*(r^2)^t + (D*B^2)*(s^2)^t

... has the forms ...

  y^2 = P + Q*u^t + R*v^t

or

  y^2 = P + Q*u^t + R*u^-t.

Strictly speaking, a Diophantine equation is an algebraic (i.e.,
polynomial) equation for which you seek integer solutions. An equation
involving exponentials is sometimes known as an exponential Diophantine
equation. But yours is mixed. Usually, two-variable Diophantine equations
(of any sort) have infinitely many solutions only when they are algebraic
of degree two or less. Therefore, if you have a more complex two-variable
equation, you should generally start by looking for some small solutions
and then try to prove that there are no solutions (if you found none) or
no more than the few that you found. (The second case is usually harder,
since the existence of even one solution often gets in the way of many
methods of proof.)

Pure exponential Diophantine equations can often be solved using modular
arithmetic, not unlike the way I solved your first equation. This is
harder when the equation has some solutions, but it can still be done. For
example, see the following two answers from our archives:

    http://mathforum.org/library/drmath/view/71960.html 
    http://mathforum.org/library/drmath/view/70360.html 

There is another strategy for solving pure exponential Diophantine
equations that involves "transcendental number theory" or "Diophantine
approximation," which essentially mean that you use some form of Baker's
Theorem on logarithmic forms (or linear forms in logarithms). See

    http://en.wikipedia.org/wiki/Transcendental_number_theory 
    http://en.wikipedia.org/wiki/Diophantine_approximation 
    http://en.wikipedia.org/wiki/Linear_forms_in_logarithms 

Unfortunately, while such methods are quite effective and can be used to
solve a wide variety of problems, they tend to require a lot of
computations, and so are really better suited to computers than to hand
calculations.

A few mixed Diophantine equations -- the kind with some algebraic and some
exponential terms -- are not too challenging. See, for example,

    http://mathforum.org/library/drmath/view/69230.html 

But the easy cases tend to be the exceptions. For example, it took years
to solve the benign equation 2^n - 7 = x^2.

    http://en.wikipedia.org/wiki/Ramanujan%E2%80%93Nagell_equation 

Modular arithmetic -- like I used for your equations -- is still a
powerful tool, as are inequalities, including the Fundamental Theorem of
Transcendental Number Theory, which states that the absolute value of a
nonzero integer is greater than or equal to 1.

The way I wrote your equation above, you have some coefficients and bases
that are not rational. Now, you *can* do modular arithmetic and
factorization and similar such things in number fields; but this becomes
much more complicated and requires extra care, since number fields don't
have all of the same properties that rational numbers and integers have.

On the other hand, many of the same ideas that apply to exponentials also
apply to sequences given by recurrence relations. And that is why I
attacked your problem using a recurrence relation and modular arithmetic.

I mentioned that having one solution can get in the way of your method of
proof. You may have noticed in some of the links above, for cases where
there were some solutions, how I used modular arithmetic in such a way
that the exponential did not repeat until it was past the solutions.
Unfortunately, your recurrence relation ...

  o(t + 2) = 3*o(t + 1) - o(t)

... is reversible:

  o(t) = 3*o(t + 1) - o(t + 2)

That means that if it is repeating for large integers t (which it will for
any modulus), then it will have been repeating the whole way from zero
(and, indeed, even continues to negative t). That means that the same
method that I described will not work when there is (at least) one
solution.

A different way to attack the problem that might work is the following.
First solve the equation

   y^2 = C + D*o^2.

A study of Pell and Pell-like equations will show that all integer
solutions (o, y) to this equation follow one of a modest list of
exponential sequences. Then you can equate each of those exponential
sequences to the exponential formula you have for o(t), and now you have a
pure exponential Diophantine equation which you can solve using Baker's
method.

Don't get me wrong. That method will get messy, but I have some confidence
that it will prove that there are no other solutions apart from the one
you built in.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 10/08/2010 at 05:31:30
From: Colin
Subject: Thank you (Find a solution to a Pell-like Diophantine equation)

Thanks you for your clear and thorough answer.

I did not know Pell equations had answers that were related to each other
in the way you described.

And knowing that I do not need the square part in o^2 is very interesting.

I am going to try to convert my mixed equation to a full exponential one
and continue from there on.
Associated Topics:
College Exponents
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/