Author |
Topic: help with eq. (Read 1732 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
help with eq.
« on: Mar 19th, 2008, 11:05pm » |
 Quote  Modify
|
Can we construct a method for finding the smallest positive integer solutions (if any) to the equation
(x-1)(y^3 -1)=x^5 -1?
If a solution does not exist, then can you find two odd prime numbers p and q such that the equation (x-1)(y^q -1)=x^p -1 does have integer solutions. If the answer is no, then consider these two equations below
(x-1)(y^q +1)=x^p -1
(x+1)(y^q -1)=x^p +1
PS: If you cannot prove that there are no solutions to any of these equations, but suspect that there aren't any, then give some of your heruistic reasons for believing in this.
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: help with eq.
« Reply #1 on: Mar 20th, 2008, 12:12am » |
Quote Modify
|
on Mar 19th, 2008, 11:05pm, BenVitale wrote:Can we construct a method for finding the smallest positive integer solutions (if any) to the equation
(x-1)(y^3 -1)=x^5 -1? |
|
How about x = y = 1?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #2 on: Mar 20th, 2008, 2:47am » |
Quote Modify
|
I assume you mean, rather, yq - 1 = xp-1+...+1.
Clearly if p=2q-1 is a Mersenne prime, then we have the solution x=1,y=2. And we always have the solution p=q, x=y=2.
If p=1 mod q, then there are at most finitely many solutions and we can find them fairly easily. In general, if f(x) is a monic polynomial of degree kd, but is not the k-th power of a polynomial, then yk=f(x) has only finitely many solutions (see here for an explanation).
But otherwise I'm not sure. For yq-1 = (xp-1)/(x-1), the only solutions for p<100, |x|<10000, x  1,2, all have p=3, y=2, and (q,x) = (13, -91), (5, -6), (3, -3), (2, -2), (5, 5), (13, 90).
For yq+1 = (xp-1)/(x-1), I found no solutions with p < 100, |x| < 10000. In any case, for each q, there are at most finitely many solutions: write p=2k+1, then
yq = x(1+x+...+xp-2) = x(1+x+...+xk-1)(1+xk).
We must have x=uq itself a perfect qth power. Now, gcd(1+x+...+xk-1, 1+xk) is either 1 or 2. It can't be 1, or else 1+uqk=vq would also be a qth power, which implies y=0 or x=0. So the gcd is 2, and either 1+ukq = 2vq or 2(1+ukq)=vq. By Thue's theorem, the equation Xq-2Yq=-1 or 2 has only finitely many solutions. Alan Baker has given an effective upper bound on any solution, so in theory we can solve this for a given prime q.
|
| « Last Edit: Mar 20th, 2008, 3:41am by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #3 on: Mar 20th, 2008, 1:06pm » |
Quote Modify
|
You wrote:
"For y^q - 1 = (x^p - 1)/(x-1), the only solutions for p<100, |x|<10000, x 1,2,
all have p=3, y=2, and (q,x) = (13, -91), (5, -6), (3, -3), (2, -2), (5, 5), (13, 90)."
I can see that you don't have p=1(mod q) in any of these cases. Furthermore, can you elaborate
on how you found these solutions? Did you use a trial and error approach or was there some
strategy?
"So the gcd is 2, and either 1+u^kq = 2v^q or 2(1+u^kq)=v^q.
By Thue's theorem, the equation X^q - 2Y^q = -1 or 2 has only finitely many solutions."
I am afraid I don't follow you here.
and is there a way to tell when you've found all the solutions for a given prime number q?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #4 on: Mar 20th, 2008, 2:01pm » |
Quote Modify
|
Yes those solutions were found by brute force. For each x and p, I found the largest power 2E dividing M= p(x)+1, and then for each q dividing E, checked if M1/q was an integer.
For the second part, we have A*B is a perfect q-th power, with gcd(A,B) either 1 or 2. So either B = vq, B = 2vq, or 2B = vq, where B = 1+xk = 1 + ukq. The first of these is impossible. In the other two cases we get a solution to Xq - 2Yq = r, with (X,Y,r) either (uk, v, -1) or (v, uk, 2). Thue has shown that, for each q, such an equation has only finitely many solutions.
Alan Baker has shown that, in theory, we can compute an effective upper bound for these solutions, but it is quite complicated and hopelessly large (2*1092 for q=19).
However, this bound has been improved. See, for example:
Yuri Bilu and Guillaume Hanrot, Solving Thue Equations of High Degree, Journal of Number Theory, Volume 60, Issue 2, October 1996, Pages 373-392.
(http://dx.doi.org/10.1006/jnth.1996.0129)
Here they explicitly solve, for example, the equation X19 - 2Y19 =  1, 2. It turns out the only solutions are the trivial ones with both |X| and |Y|  1, so the only solutions to the original problem with q=19 are
{p,x,y}
{p,0,0}
{p,-1,0}
{2,1,2}
To find the bound for Xq - 2Yq = C, you will first need to compute a set of (q-1)/2 fundamental units for the field K= (21/q), as well as all solutions to NK/Q( ) = C, for in the ideal (1,21/q).
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #5 on: Mar 20th, 2008, 5:54pm » |
Quote Modify
|
You wrote:
"For each x and p, I found the largest power 2^E dividing M = Phi_p (x)+1,"
I see, so first you just pick two numbers at random and denote them as your x and p values and then go from there.
What does p(x) represent?
Theres a lot of theory you appear to be using which I don't recognize. Is this theory from the theory of higher order Diophantine equations or perhaps algebraic number theory ?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #6 on: Mar 20th, 2008, 6:13pm » |
Quote Modify
|
All the solutions I've found have been for p=3:
yq = x2 + x + 2, or
4yq = (2x+1)2 + 7 = m2 + 7.
Let  =  {-7}. The ring of integers of K = () is R =  [], where = (1+)/2, and this is a UFD. Over this ring, the (rational) prime 2 splits as ', where ' = (1-)/2. And 7 ramifies as 7 = -2. Now consider
yq = [(m+)/2][(m-)/2].
If a prime p | ([(m+)/2], [(m-)/2]), then p | . But if | m+, then |m, and since m is an integer, 7|m, making m2+7 divisible by 7 but not 72, so it can't be a q-th power. So these two factors are relatively prime. Since the only units of R are 1, we must have
(m+)/2 = zq
for some z = (a+b)/2  R. Since q is odd, we can switch the sign of z if necessary, and then we need to solve the equation
7/2 = Im[((a + b)/2)q].
For each q, this equation takes the form
b*f(a,b) = 2q-1,
where f is an integer polynomial. So b|2q-1, and for each choice of b (in fact, we can show b=(q|7)=1), see if f(a,b)=2q-1/b has an integer solution (using the rational roots theorem, say), and in this way find all the solutions for a given q.
For q=3, we get
b(3a2-7b2) = 4,
and find b=-1, a=1, so
m = 2Re[((1 - {-7})/2)3] = 5,
corresponding to x=2, -3, and y=2.
For q=5, the equation becomes
b(5a4-70a2b2+49b4) = 16,
and we again find a=1, b=-1, giving x=5, -6, and y=2.
Similarly for q=13, there is only y=2, x=90, -91.
There are no other solutions for q < 100. And there are no other solutions with y=2 for q <106, which isn't surprising:
If y=2, then (m+)/2 must be a power of or '. Writing = 2 ei , we would need 2q/2sin(q) = 7/2, so for some integer n,
|q- n | < |sin(q)| = 7/2 * 1/2q/2,
or
|/- n/q| < 7/2 * 1/(q2q/2),
which is quite unlikely for large q (if were chosen at random, then with probability 1, this equation would have only finitely many solutions). If there were infinitely many solutions, / would be a Liouville number (but we already know / is transcendental, since ei is algebraic but not a root of unity).
|
| « Last Edit: Mar 20th, 2008, 9:01pm by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #7 on: Mar 20th, 2008, 6:55pm » |
Quote Modify
|
on Mar 20th, 2008, 5:54pm, BenVitale wrote:| I see, so first you just pick two numbers at random and denote them as your x and p values and then go from there. |
|
Yes. Given p and x, we can quickly find a very small set of possibilities for q.
Quote:| What does p(x) represent? |
|
n(x) denotes the n-th cyclotomic polynomial. For p prime, p(x) = (xp-1)/(x-1).
Quote:| Theres a lot of theory you appear to be using which I don't recognize. Is this theory from the theory of higher order Diophantine equations or perhaps algebraic number theory ? |
|
Yes, Diophantine approximation. To understand the proofs, a basic course in algebraic number theory is essential (ring of integers, class group, unit group, etc. of a number field).
Thue's theorem is closely related to the Thue-Siegel-Roth theorem. For example, in our case:
C = Xq - 2Yq = Yq(X/Y-21/q)(X/Y-21/q )...(X/Y-21/qq-1),
where =e2i/q is a q-th root of unity. For X,Y integers, and 0<i<q, |X/Y-i 21/q| > K for some constant K, and so we get
|X/Y-21/q| < (C/Kq-1)*1/Yq,
which has only finitely many solutions by Thue-Siegel-Roth. However, Thue-Siegel-Roth is computationally ineffective. What Alan Baker did was prove an effective lower bound on the values of linear forms in logarithms.
For example, if , ' are algebraic, with log, log' linearly independent over , then log, log' are linearly independent over the algebraic closure of (this is equivalent to the Gelfond-Schneider theorem). What Baker did was give an effective lower bound on the value of an expression like
|1log1 + ... + nlogn|,
where i,i are in some number field K.
|
| « Last Edit: Mar 20th, 2008, 11:53pm by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #8 on: Mar 21st, 2008, 10:31am » |
Quote Modify
|
why did you initially recommend that we have p=1 mod q? Was this only for finding solutions to (x-1)(y^q +1)=x^p -1?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #9 on: Mar 21st, 2008, 10:51am » |
Quote Modify
|
I didn't recommend that p=1 mod q, I just pointed out that if p=1 mod q, then we can easily show there are only finitely many solutions, and give an effective procedure for finding them, if they exist.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #10 on: Mar 21st, 2008, 12:23pm » |
Quote Modify
|
Okay. Thanks.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #11 on: Mar 21st, 2008, 2:49pm » |
Quote Modify
|
If we need to find two pairs of integers (a,b) and (x,y) such that the following holds:
x^3 + y^3 = a^5 + b^5.
And, generally, can we find integer solutions to
x^p + y^p = a^q + b^q
for some two odd primes p and q ?
Is the solution x=c^q, y=d^q, a=c^p, b=d^p ?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #12 on: Mar 21st, 2008, 5:33pm » |
Quote Modify
|
on Mar 21st, 2008, 2:49pm, BenVitale wrote:
This one, at least, will have a lot of solutions not of the form U15+V15.
For example, suppose we have a solution to (n+1)3-n3 = y2. This can be rearranged to (2y)2 - 3(2n+1)2 = 1, which is Pellian, and easily solved. The first few solutions to this are
{n, y} = {0, 1}, {7, 13}, {104, 181}, {1455, 2521}, {20272, 35113}, {282359, 489061}, {3932760, 6811741}, {54776287, 94875313}, ...
Now ((n+1)y)3 + (-ny)3 = y5 + 05.
And if we want non-zero solutions, we can write this as
(4(n+1)y)3 + (-4ny)3 = (2y)5 + (2y)5.
But there are less trivial solutions. For example,
(-4)3 + 113 = 35 + 45
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #13 on: Mar 21st, 2008, 5:43pm » |
Quote Modify
|
Actually, for any four integers (x,y,a,b), we can always find a solution of the form (Mx,My), (Na,Nb) for integers M,N.
Let r = (aq+bq)/(xp+yp).
WLOG, suppose r > 0. Suppose the prime s appears with exponent k (positive or negative) when r is factored into primes. Since p and q are relatively prime, we can always find positive integers u,v such that pu-qv = k. So if we let
M =  s su, and N = s sv, then Mp/Nq = s sk = r.
Therefore (Mx)p + (My)p = (Na)q + (Nb)q.
|
| « Last Edit: Mar 21st, 2008, 5:45pm by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #14 on: Mar 23rd, 2008, 4:38pm » |
Quote Modify
|
Going back to the equation yq - 1 = p(x) for a moment:
Other than (x,y,p,q) = (1,2,2q-1,q) and (2,2,p,p), the only solutions I've found have been for p=3, y=2. In this case, the equation can be written 2q+2 - 7 = (2x+1)2, which is the Ramanujan-Nagell equation. Indeed the only solutions with q an odd prime are q = 3,5,13, as found. A proof can be found here (Theorem 64 on page 50).
But lets consider the case p=q=3, which we can write as Y2 = X3 - 7*16, where Y=8x+4, X=4y. This is an elliptic curve, and the set of rational points on this curve form a finitely generated abelian group. We can show this group is isomorphic to , generated by the point P = (8,20), corresponding to (x,y)=(2,2). The first few multiples of P are
2P = (176/25, -1924/125)
3P = (12097/9, -1330505/27)
4P = (53492384/5784025, 362481051652/13910580125)
5P = (570448961048/90505307281, -320312296066502900/27227707147723321)
So there are infinitely many rational solutions, but they get large (in terms of height) very fast. And, as in any elliptic curve over , there are at most finitely many integer points.
When p=3, I gave an effective procedure to find all solutions for a given q. But by a theorem of Siegel (which I believe Baker has made effective, in theory), if q  3, and f(x) has at least 2 simple roots, then
yq = f(x)
has at most finitely many solutions. Letting f(x)=1+p(x), we can show f and f' have no common root: If f(x)=0, then xp = 2-x, and then f'(x)=0 gives x=1 or 2p/(p-1). But x=1 is not a root of f(x), and x=2p/(p-1) is not either (clear if p=3, or by the rational roots theorem if p>3). So f(x) has p-1 distinct roots over  , and the theorem applies.
In fact, the theorem also applies when q=2 and f has at least 3 simple roots, which requires p > 3. [Note that, if q=2 and f(x) = dx2 + 1, say, with d square free, then this is a Pell equation, and has infinitely many integer solutions, but they grow exponentially.]
So in either case, yq 1 = p(x) has only finitely many solutions for a given p,q.
|
| « Last Edit: Mar 23rd, 2008, 5:00pm by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #15 on: Mar 25th, 2008, 10:34am » |
Quote Modify
|
You wrote
"Actually, for any four integers (x,y,a,b), we can always find a solution of the form (Mx,My), (Na,Nb) for integers M,N.
Let r = (a^q + b^q)/(x^p + y^p)."
What if r is not an integer?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #16 on: Mar 25th, 2008, 3:05pm » |
Quote Modify
|
on Mar 25th, 2008, 10:34am, BenVitale wrote:| What if r is not an integer? |
|
I didn't assume it was. That's why I said:
on Mar 21st, 2008, 5:43pm, Eigenray wrote:| Suppose the prime s appears with exponent k (positive or negative) when r is factored into primes. |
|
The only assumption I made was that xp+yp and aq+bq were non-zero.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #17 on: Mar 25th, 2008, 8:48pm » |
Quote Modify
|
Sorry.
How can you find integers (a,b,x,y) say p=17 and q=13 s.t.
a^13 + b^13 = x^17 + y^17
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: help with eq.
« Reply #18 on: Mar 26th, 2008, 1:17am » |
Quote Modify
|
Take, say, a=1,b=2, x=1,y=2. Then
(213+1)/(217+1) = 2731 / 43691 = u/v.
Since 10*17 - 13*13 = 1, and 3*17 - 4*13 = -1, let M=u10v3, N=u13v4. Then
M17 + (2M)17 = N13 + (2N)13.
It is probably more interesting then to look for solutions with (x,y)=1 and (a,b)=1.
|
| « Last Edit: Mar 26th, 2008, 1:18am by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #19 on: Apr 27th, 2008, 12:37pm » |
Quote Modify
|
I'm requesting help with the following equation:
x = 5(1-e^(-x) )
My question: is there a way to solve for x analytically?
I don't see how this equation can be solve analytically in terms of elementary.
Perhaps, in terms of the Lambert W-function, x = 5 + W(-5e^-5)
Your thoughts, please.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: help with eq.
« Reply #20 on: Apr 27th, 2008, 1:23pm » |
Quote Modify
|
Don't forget x = 0. 
The Lambert W function is a funny old thing. It's a little like square roots: notation introduced to "solve" something that cannot really be solved analytically. I find it all rather circular...
"Find the positive root to the equation, x2 = 2."
"Well, x = sqrt(2)."
"And what is the square root of two?"
"It's a number which when squared equals two."
"But isn't that what I said originally?"
(Braces himself for a reaction.)
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: help with eq.
« Reply #21 on: Apr 27th, 2008, 3:58pm » |
Quote Modify
|
on Apr 27th, 2008, 1:23pm, Sir Col wrote:
(Braces himself for a reaction.) |
|
I agree, Sir Col.
Green readers in favour of recycling may like this.
|
| « Last Edit: Apr 27th, 2008, 10:36pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #22 on: Apr 27th, 2008, 5:00pm » |
Quote Modify
|
on Apr 27th, 2008, 3:58pm, ThudanBlunder wrote:
I agree Sir Col.
Green readers in favour of recycling may like this.
|
|
Thanks for the link
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #23 on: Apr 27th, 2008, 5:03pm » |
Quote Modify
|
on Apr 27th, 2008, 1:23pm, Sir Col wrote:Don't forget x = 0.
The Lambert W function is a funny old thing. It's a little like square roots: notation introduced to "solve" something that cannot really be solved analytically. I find it all rather circular...
"Find the positive root to the equation, x2 = 2."
"Well, x = sqrt(2)."
"And what is the square root of two?"
"It's a number which when squared equals two."
"But isn't that what I said originally?"
(Braces himself for a reaction.) |
|
That's how I felt about the error function when I first learned about it in probability.
The equation is not algebraic, but transcendental, so can we say that it doesn't have an analytical solution.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: help with eq.
« Reply #24 on: Apr 27th, 2008, 8:28pm » |
Quote Modify
|
How about
Graphing x/5 and (1-e^(-x)) it appears the only point of intersection is near x=5. I don't think there's any way to express the exact answer in terms of elementary functions and constants, but one way of getting an approximate answer is to expand both sides near x=5 and use algebraic methods. For example defining x = 5 + u, the equation becomes:
1 + u/5 = 1 - e^(-5)(1 - u + u^2/2! - u^3/3! + ...)
Since x ~ 5, u is small so ignoring u^2 and higher powers of u this is *approximately* :
(e^5/5)-1)u + 1 = 0
x --> 5 - 5/(e^5 - 5)
"A dictionary of real numbers" by Borwein and Borwein has no close candidate formula for the value 4.9651142... , which is approximately the non-origin intersection of the two curves. This is proves that it's not easy, even if it's possible.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print