Pell-like Diophantine EquationsDate: 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. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/