None of this nursery school stuff - a proper maths problem. 25$ reward

[Rotating Rabbit]

X^2 + 68 = Y^5

Find all the solutions or prove there are none.

25$ via neteller for the first correct answer.

(So if you have finite solutions you must list and show they solve the equation and also prove no others work. Or if you have an infinite set X of solutions you must show that all solutions from set X are roots, and prove no others work. Or you must prove there are no solutions)

[ihardlyknowher]

There are infinite solutions, since every number > or = 68 has a defined 5th root.

In other words, let X = x and Y=(x^2+68)^(1/5).

The has a solution for any integer x.

[jason_t]

[ QUOTE ]
X^2 + 68 = Y^5

Find all the solutions or prove there are none.

25$ via neteller for the first correct answer.

(So if you have finite solutions you must list and show they solve the equation and also prove no others work. Or if you have an infinite set X of solutions you must show that all solutions from set X are roots, and prove no others work. Or you must prove there are no solutions)

[/ QUOTE ]

I think that you intended to state the solutions should be natural numbers otherwise the problem is uninteresting.

[jason_t]

[ QUOTE ]
There are infinite solutions, since every number > or = 68 has a defined 5th root.

In other words, let X = x and Y=(x^2+68)^(1/5).

The has a solution for any integer x.

[/ QUOTE ]

I think he intended for both x and y to be natural numbers.

[gumpzilla]

It's supposed to be a Diophantine equation, he wants solutions for integer X and Y. Doesn't seem like the most thrilling problem in the world, and involves more technical knowhow than counting triangles.

[Rotating Rabbit]

Yeah sorry I (obviously) meant X and Y natural numbers. And I intend to pay up unlike KKF btw.

[MrWookie47]

Y = (X^2+68)^(1/5) describes a curve with a domain of the entire set of real numbers. There are infinite solutions. However, since this is a 5th root, there are 4 additional solutions that each yield the same value of y when one considers numbers in the imaginary plane. The set of roots in the imaginary plane, when described in polar coordinates, will have the same radius as the real solution, and will have their angles spaced equidistantally around 2*pi radians. The set of all roots can be described by

(x^2 + 68)^(1/5) * exp(i * 2*pi*n/5)

where n is 1, 2, 3, 4, or 5 (or any integer, I suppose), i is the sqrt(-1), and x is any real number.

Edit: Crap. I guess this problem is hard because he wanted the natural number solutions, not the imaginary ones.

[jason_t]

[ QUOTE ]

Edit: Crap. I guess this problem is hard because he wanted the natural number solutions, not the imaginary ones.

[/ QUOTE ]

Yes. Diophantine equations, of which this is an example, are extremely difficult to solve. Fermat's last theorem is another example. A famous problem of Hilbert, that has been solved, qualifies exactly how difficult they are to solve: there will never ever be a computer algorithm capable of solving all Diophantine equations.

[TheIrishThug]

x^2+68-y^5
x=+/- (y^5-68)^1/2
y has to be >= 68^1/5
x can be any real number

edit: so there r an infinite solution, but with the range of y>=68^1/5

[Patrick del Poker Grande]

[ QUOTE ]
the problem is uninteresting.

[/ QUOTE ]

[jason_t]

[ QUOTE ]
x^2+68-y^5
x=+/- (y^5-68)^1/2
y has to be >= 68^1/5
x can be any real number

[/ QUOTE ]

No, x can not be. I assure you that the OP meant, as he clarified later, for x and y to be natural numbers. Otherwise the problem is incredibly uninteresting and not related to any entire body of mathematics called Diophantine equations which is clearly what he intended.

[ihardlyknowher]

[ QUOTE ]
[ QUOTE ]
the problem is too difficult for me.

[/ QUOTE ]

[/ QUOTE ]

FYP

[GFunk911]

I'm assuming X and Y are integers?

Edit: nm, clicked reply when there were no replies

[ThaSaltCracka]

[censored], if I had my TI-92 or whatever its called, I could figure this out.

[TheIrishThug]

yeah, i just googled Diophantine equations. this is way over my head. u guys have fun.

[durron597]

Why do I think this is one of those "unanswered" problems that gets a million bucks if the correct answer is published.

[hotsauce615]

We need matt damon

[jakethebake]

[ QUOTE ]
We need matt damon

[/ QUOTE ]

I expect his gimmick account any moment.

[citanul]

[ QUOTE ]
Why do I think this is one of those "unanswered" problems that gets a million bucks if the correct answer is published.

[/ QUOTE ]

it's not. it's just some random diophantine equation.

citanul

[Arnfinn Madsen]

I am a born mathematical genius (solved high school problems at age of 7) but haven't kept up with it lately. My intuition though tells me there are no solutions without quite finding the proof in my head.

So I will offer my 2 cents to lay the foundation for somebody else. When you ^2 a number you basically just double up the number of factors it consist of (i.e. 30=2*3*5 while 900=2*2*3*3*5*5). When you add 68 you add 2*2*17. The number you get after adding 68 has to contain a number of each factor dividable by 5. I think the assymetric nature of 68 containing of 1 factor of 1 kind and 2 of the other messes that up.

No proof, so I don't claim the $25.

EDIT: Just for clarification I know that addition does not mean that you add the factors (that is multiplying), so somebody need to look into the effect of adding the assymetric number of 68.

[jason_t]

[ QUOTE ]
I am a born mathematical genius (solved high school problems at age of 7) but haven't kept up with it lately. My intuition though tells me there are no solutions without quite finding the proof in my head.

So I will offer my 2 cents to lay the foundation for somebody else. When you ^2 a number you basically just double up the number of factors it consist of (i.e. 30=2*3*5 while 900=2*2*3*3*5*5). When you add 68 you add 2*2*17. The number you get after adding 68 has to contain a number of each factor dividable by 5. I think the assymetric nature of 68 containing of 1 factor of 1 kind and 2 of the other messes that up.

No proof, so I don't claim the $25.

EDIT: Just for clarification I know that addition does not mean that you add the factors (that is multiplying), so somebody need to look into the effect of adding the assymetric number of 68.

[/ QUOTE ]

This type of reasoning doesn't work.

29 + 3 is divisible two even though neither term is and in fact both terms are prime.

[[censored]]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
My brain hurts[/b].

[/ QUOTE ]

[/ QUOTE ]

FYP

[/ QUOTE ]

[Arnfinn Madsen]

You are right Jason, flaw in my intuition, so now you led me to the correct answer. There are an infite number of primes. When you ^2 a prime you end up with infinite amount of numbers. These are basically random since the distribution of primes is random. random+68=random. Thus x^2+68 leads to an infinite amount of random numbers. An infinite amount of random numbers will have infinite numbers that corresponds to y^5.

So, the numbers of solutions are infinite. Send me $25.

[jason_t]

[ QUOTE ]
You are right Jason, flaw in my intuition, so now you led me to the correct answer. There are an infite number of primes. When you ^2 a prime you end up with infinite amount of numbers. These are basically random since the distribution of primes is random. random+68=random. Thus x^2+68 leads to an infinite amount of random numbers. An infinite amount of random numbers will have infinite numbers that corresponds to y^5.

So, the numbers of solutions are infinite. Send me $25.

[/ QUOTE ]

Sorry, but that also doesn't work, even on an intuitive level, because the set of natural numbers that is of the form y^5 is very sparse in the set of all natural numbers: a random set of natural numbers (in this case, those of the form x^2 + 68) could avoid all natural numbers of the form y^5.

[Arnfinn Madsen]

[ QUOTE ]
[ QUOTE ]
You are right Jason, flaw in my intuition, so now you led me to the correct answer. There are an infite number of primes. When you ^2 a prime you end up with infinite amount of numbers. These are basically random since the distribution of primes is random. random+68=random. Thus x^2+68 leads to an infinite amount of random numbers. An infinite amount of random numbers will have infinite numbers that corresponds to y^5.

So, the numbers of solutions are infinite. Send me $25.

[/ QUOTE ]

Sorry, but that also doesn't work, even on an intuitive level, because the set of natural numbers that is of the form y^5 is very sparse in the set of all natural numbers: a random set of natural numbers (in this case, those of the form x^2 + 68) could avoid all natural numbers of the form y^5.

[/ QUOTE ]

You were right last time, but now I think you are wrong. There is no sparsity of number that corresponds to y^5. There is infinite Ys, so there is infinite Y^5's. Sooner or later the x^2+68 will hit, and since it gets infinite chances it will hit infinite times.

[gumpzilla]

One trick similar to what I think you were trying to do that sometimes works to prove there are no solutions is to use modular arithmetic. Consider the Diophantine equation x^2 + 1 = 3y. We can prove there are no integers x, y that solve this. How? We know that x^2 + 1 must be divisible by 3. But if x is an integer, then it will be congruent to 0, 1, or 2 mod 3. (This means it will have remainder 0, 1, or 2 when you divide it by 3) No matter which one you pick, you can't get x^2 + 1 to be divisible by 3. So there are no integer solutions. In this case, I don't think this will be very helpful, though.

[mslif]

[ QUOTE ]
X^2 + 68 = Y^5

Find all the solutions or prove there are none.

25$ via neteller for the first correct answer.

(So if you have finite solutions you must list and show they solve the equation and also prove no others work. Or if you have an infinite set X of solutions you must show that all solutions from set X are roots, and prove no others work. Or you must prove there are no solutions)

[/ QUOTE ]

I have just spent almost an hour on this. I am not giving up! I am too invested now.....

[Arnfinn Madsen]

[ QUOTE ]
One trick similar to what I think you were trying to do that sometimes works to prove there are no solutions is to use modular arithmetic. Consider the Diophantine equation x^2 + 1 = 3y. We can prove there are no integers x, y that solve this. How? We know that x^2 + 1 must be divisible by 3. But if x is an integer, then it will be congruent to 0, 1, or 2 mod 3. (This means it will have remainder 0, 1, or 2 when you divide it by 3) No matter which one you pick, you can't get x^2 + 1 to be divisible by 3. So there are no integer solutions. In this case, I don't think this will be very helpful, though.

[/ QUOTE ]

No, it will not help now. What I forgot, which Jason pointed out, is that prime distribution is random. Thus there does not need to be any logical connection between x and y. Left side of equation is an unsystematic amount of infinite numbers as is right side of equation. Thus they match eachother i.e. infinite/1,000,000,000 times. Since infinite/1,000,000,000=infinite; there is infinite solutions.

[gumpzilla]

[ QUOTE ]

No, it will not help now. What I forgot, which Jason pointed out, is that prime distribution is random. Thus there does not need to be any logical connection between x and y. Left side of equation is an unsystematic amount of infinite numbers as is right side of equation. Thus they match eachother i.e. infinite/1,000,000,000 times. Since infinite/1,000,000,000=infinite; there is infinite solutions.

[/ QUOTE ]

Huh? This doesn't make sense and it doesn't reference the given Diophantine equation, so I can only assume you're talking about all equations of this form. As I pointed out, x^2 + 1 = 3y has no solutions with x,y integer. I invite you to produce a counterexample if you think I am wrong.

[Arnfinn Madsen]

[ QUOTE ]
[ QUOTE ]

No, it will not help now. What I forgot, which Jason pointed out, is that prime distribution is random. Thus there does not need to be any logical connection between x and y. Left side of equation is an unsystematic amount of infinite numbers as is right side of equation. Thus they match eachother i.e. infinite/1,000,000,000 times. Since infinite/1,000,000,000=infinite; there is infinite solutions.

[/ QUOTE ]

Huh? This doesn't make sense and it doesn't reference the given Diophantine equation, so I can only assume you're talking about all equations of this form. As I pointed out, x^2 + 1 = 3y has no solutions with x,y integer. I invite you to produce a counterexample if you think I am wrong.

[/ QUOTE ]

You are right in your example. I guess I did not formulate well enough so I will try again:

Those x's that are interesting to look at are prime numbers. All others are fairly uninteresting. When you add 68 to x^2 you completely mess up the factors. Just try i.e. x=5. x^2=25=5*5 while x^2+68=3*31. For different x's the adding of 68 will work differently since this game is about trying to get the left side to be a number consisting of a dividable number of 5 of each factor. In your example the +1 destroys the possibility of reaching a number dividable by 3, here adding 68 is basically throwing all the factors up into the air. A few times they will land right.

[sirio11]

Solved !!!! Modulo 11, let me check the proof.

There are no solutions

[sirio11]

x^2 + 68 = y^5 then

x^4 + 136x^2 + 68^2 = y^10

Now working modulo 11

By Little Fermat theorem, y^10 = 1 if (y,11)=1

68=2 68^2=4 136 = 4 then

x^4 + 4x^2 + 4 = 1 mod 11

(x^2 + 2)^2 = 1 mod 11

therefore x^2 + 2 = 1 so x^2 = -1 mod 11

or x^2 + 2 = -1 this is x^2 = -3 = 8 mod 11

contradiction in both cases!!!

Now, if y = 11k then y = 1 mod 10

so, x^2 + 68 = 1 mod 10

x^2 - 2 = 1 mod 10

x^2 = 3 mod 10 contradiction !!!

Q.E.D.

David

[Arnfinn Madsen]

I am an idiot, I confess /images/graemlins/smile.gif.

nh.

[mslif]

very nice

[gumpzilla]

Ha! I gave up at 7. Guess I should have gone one prime more.

[pzhon]

[ QUOTE ]

Now, if y = 11k then y = 1 mod 10


[/ QUOTE ]
What?

[gumpzilla]

[ QUOTE ]
[ QUOTE ]

Now, if y = 11k then y = 1 mod 10


[/ QUOTE ]
What?

[/ QUOTE ]

Good call. I missed that when I was looking over his argument.

[pzhon]

Here is a relevant reference. I don't know whether this contains the solution, but it reduces the problem to a finite search:

<ul type="square">MR1259344 (94k:11037)
Cohn, J. H. E.(4-LNDHB)
The Diophantine equation $x\sp 2+C=y\sp n$.
Acta Arith. 65 (1993), no. 4, 367--381.
11D61

--------------------------------------------------------------------------------
It follows from the theory of linear forms in logarithms that for a nonzero integer $C$, the equation (1) $x^2+C=y^n$ in integers $x,y,n\geq 2$ implies that $\max$ $(|x|,|y|,n)$ is bounded by an effectively computable number depending only on $C$. The value of this number turns out to be very large. For several values of $C$, all the solutions of equation (1) have been determined. For example, if $C=11,17,40$, the only solutions of (1) are given by $x=4$ and $x=58$, $x=8$ and $x=52$, respectively. Furthermore, 46 values of $C\leq 100$ are given for which equation (1) has no solution. The paper contains an account of earlier results on equation (1).[/list]

[sirio11]

[ QUOTE ]
[ QUOTE ]

Now, if y = 11k then y = 1 mod 10


[/ QUOTE ]
What?

[/ QUOTE ]

Damm it

[Rotating Rabbit]

Hey,

Some good efforts, particularly from Sirio (&amp; Gump). Arfinn you've got intuition I suspect, but this problem is too hard to be able to intuitively 'suspect' there are/arent solutions (unless your life is diophantine equations, then maybe). Modulo reduction and arithmetic is a useful tool in number theory, only trouble is that its limited mostly to proof by contradiction, not much good if there are actually roots!

But in fact there arent any roots in this one, so if you look hard enough it might be possible to find a series of reductions to prove the non-existance of solutions. I dont know how far one has to look (potentially for ever) because I havnt proved it this way.

In fact the problem is not easy, and I think in hindsight perhaps too difficult, so I'll give a very rough solution tomorrow if anyone's interested. For those still thinking, here are some clues:

<font color="white">

Work in the field Z[sqrt(-17)]: (that is to say, all numbers in this field have the form 'a + b.sqrt(-17)' where a and b are in Z.

Then the equation is x+2.sqrt(-17) * x-2.sqrt(-17) = y^5

Lets let A = x + 2.sqrt(-17).

Now it is possible to show, by considering the factorisation of y^5, that A itself is a fifth power in this field. This is difficult.

But it is possible, and indeed: A = (c + d.sqrt(-17))^5 with c and d integers. From this, you can show there are no solutions by expanding and looking for a condradiction. </font>

[PairTheBoard]

More problems like this please:

http://forumserver.twoplustwo.com/showthreaded.php?Cat=&amp;Number=2787013&amp;page=&amp;view=&amp;s b=5&amp;o=

PairTheBoard

[pzhon]

[ QUOTE ]

Lets let A = x + 2.sqrt(-17).

Now it is possible to show, by considering the factorisation of y^5, that A itself is a fifth power in this field. This is difficult.

[/ QUOTE ]
Is there unique prime factorization in Z[sqrt(-17)]?

My approach was to note that y must be divisible by 11, then to try to factor the ideal &lt;11&gt;, with the idea of trying to show that A is divisible by 11. However, I believe the ideal &lt;11&gt; factors by duality, since x^2+17 factors mod 11.

[jason_t]

[ QUOTE ]
x^2 + 68 = y^5 then

x^4 + 136x^2 + 68^2 = y^10

Now working modulo 11

By Little Fermat theorem, y^10 = 1 if (y,11)=1

68=2 68^2=4 136 = 4 then

x^4 + 4x^2 + 4 = 1 mod 11

(x^2 + 2)^2 = 1 mod 11

therefore x^2 + 2 = 1 so x^2 = -1 mod 11

or x^2 + 2 = -1 this is x^2 = -3 = 8 mod 11

contradiction in both cases!!!

Now, if y = 11k then y = 1 mod 10

so, x^2 + 68 = 1 mod 10

x^2 - 2 = 1 mod 10

x^2 = 3 mod 10 contradiction !!!

Q.E.D.

David

[/ QUOTE ]

First, I think this the right approach and what I was trying earlier but

y = 11k then y = 1 mod 10

is incorrect

and I think we should be working modulo 17 (prime factor of 68), not modulo 11.

[jason1990]

[ QUOTE ]
Is there unique prime factorization in Z[sqrt(-17)]?

[/ QUOTE ]
Theorem 8.22 of An Introduction to Number Theory, Harold M. Stark:
If d&lt;0, then Q(\sqrt{d}) has the unique factorization property if and only if d is one of the nine numbers -1,-2,-3,-7,-11,-19,-43,-67, and -163.

[Rotating Rabbit]

[ QUOTE ]
[ QUOTE ]
Is there unique prime factorization in Z[sqrt(-17)]?

[/ QUOTE ]
Theorem 8.22 of An Introduction to Number Theory, Harold M. Stark:
If d&lt;0, then Q(\sqrt{d}) has the unique factorization property if and only if d is one of the nine numbers -1,-2,-3,-7,-11,-19,-43,-67, and -163.

[/ QUOTE ]

Exactly. Unfortunately, -17 not equal to 1 mod 4, which effectively destroys any chance of the ring of integers of Q(sqrt(-17)) being a UFD.

(Briefly, this is because the ring is too small. Note that if a = c + d.sqrt(-17) and b = c - d.sqrt(-17) then (X - a)(X - b) = X^2 - 2cX + c^2 - 17d^2 as the minimum polynomial doesnt have many roots as T =( 1 + sqrt(-17) / 2 ) doesnt solve the above). So finding a euclidean norm is impossible here. For positive values in the sqrt matters get even worse...)

But its still possible to navigate around this. But as I said this problem is way too hard, which is my fault.