| Posted on Thursday, 12 June, 2003 - 09:25 pm: |
Anyone got any hints for me?
Find all triples (x,y,z) of positive integers such that y is a prime number, z is not divisible by either 3 or y, and x3 -y3 =z2 .
Any help would be appreciated.
Thanks,
Peter
good luck to all doing P5 tomorrow
| Posted on Thursday, 12 June, 2003 - 09:59 pm: |
Surely there are no such triples, since x3 = y3 + z3 and this is a case of Fermat's Last Theorem?
| Posted on Thursday, 12 June, 2003 - 10:05 pm: |
Apologies, I read the question wrong
| Posted on Thursday, 12 June, 2003 - 10:05 pm: |
"x3 -y3 =z2 "
| Posted on Thursday, 12 June, 2003 - 10:05 pm: |
Thanks Phil
| Posted on Friday, 13 June, 2003 - 12:45 pm: |
I think there are no such triples:
The left hand side factorises giving
(x-y)(x2 +xy+y2 )=z2 (*)
Now x3 -y3 =z2 > 0
so x> y
x-y> 0
x-y < (x-y)2 < x2 +y2 +xy
(so x2 +y2 +xy is a multiple of z. I'm not sure that it matters though - just that it's bigger than x-y)
let x2 +y2 +xy=kz, where k is a positive integer
so that x-y=z/k
so k2 (x-y)=x2 +y2 +xy
so (x-y) is a factor of (x2 +y2 +xy)
so (x2 +y2 +xy)/(x-y) is a whole number
(x2 +y2 +xy)/(x-y)=x-y+3xy/(x-y)
therefore 3xy is a multiple of (x-y)
therefore (x-y) is divisible by 3
therefore 3 is a factor of z2
therefore z is a multiple of 3
but that's not allowed
and sorry in advance - I'm quite likely to have made a stupid mistake somewhere! love Sarah
| Posted on Friday, 13 June, 2003 - 01:45 pm: |
Sarah,
I've just found using a calculator and a bit of trial and error that 83 -73 = 132 , and so i don't think your method can be right. How did you conclude that x2 + y2 + xy is a multiple of z?
Peter
| Posted on Friday, 13 June, 2003 - 04:44 pm: |
I have a proof that (8,7,13) is the only solution. The proof uses some properties of the Eisenstein integers - do you know what they are?
Kerwin
| Posted on Friday, 13 June, 2003 - 06:17 pm: |
Let w = exp(2pi/3). Then you can check that w3=1, w2+w+1 = 0 and that the original equation can be written as: (x-y)(x-wy)(x-w2 y)=z2 The Eisenstein integers that Kerwin refers to, are the set of all numbers of the form a+bw+cw2 where a, b, c are integers. [Or equivalently all numbers of the form A+Bw] These behave very much like the ordinary integers and they also have the unique factorization property. The conditions of the problem ensure that the factors x-y, x-wy, x-w2 y are pairwise coprime. (z not divisible by 3 is important here) Because uniqueness of factorization holds in the Eisenstein integers each of (x-y), x-wy, x-w2 y is a perfect square. [This means of the form (a+bw)2 where a and b are integers.] Can you try and finish the problem now? Demetres
| Posted on Friday, 13 June, 2003 - 06:28 pm: |
Just have to be careful with the two factors x-wy and x-w2 y: you also need to consider the case -(a+bw)2. Kerwin
| Posted on Friday, 13 June, 2003 - 07:20 pm: |
True, each of these factors are (unit)*(perfect square) not just a perfect square. The units are: 1, -1, w, -w, w2, -w2 As (1+w)2=w, then as Kerwin said, we also need to consider the case -(a+bw)2 as well. Ask if anything is not clear in my last two posts. [I stated lots of results without any explanation.] Demetres
| Posted on Friday, 13 June, 2003 - 11:13 pm: |
whoops, how embarrassing. You didn't mention my other dazzling non sequitur:
"3xy is a multiple of (x-y) therefore (x-y) is divisible by 3"
hmm need some sleep
love Sarah
| Posted on Saturday, 14 June, 2003 - 12:57 am: |
I've never met Eisenstein integers before, so a few questions about them first, before I do the problem: quote: The Eisenstein integers that Kerwin refers to are the set of all numbers of the form a+bw +cw2 where a, b, c are integers. [Or equivalently all numbers of the form A+Bw] Are ''Eisenstein integers'' actual integers or complex numbers that behave like integers? Is w always exp(2pi/3) or can it be any exp(kpi) number, or even any complex number? If ''Eisenstein integers'' just behave like integers but are in fact complex, are there ''Eisenstein primes'', for the unique factorization? Thanks for the help Peter (The problem came from a BMOC Mentoring Scheme Sheet which I use to get emailed to me but I never did this sheet. I recently decided to start working through a few of the problems, and dug the sheet up from the bottom of my inbox.)
| Posted on Saturday, 14 June, 2003 - 10:17 am: |
Good questions Peter.
Eisenstein integers behave like integers:
Try to check the following:
1)If you add, subtract, multiply two of them, you get another Eisenstein integer. [no division]
2)If a,b are Eisenstein integers and a.b = 0 then either a = 0 or b = 0 (This is trivial)
Theorem: Suppose f is a polynomial with integer coefficients and leading coefficient 1. Then if f has a rational root x, x is an integer.
I guess you have seen that theorem again. If not try to prove it.
Now try to show that given an Eisenstein integer a + bw, there is a polynomial f, (of degree 2) with intger coefficients, leading coefficient 1 with f(a + bw) = 0
This is the reason they are called integers.
This also suggest that we might be able to do arithmetic with them as we do with ordinary integers.
w in this case is exp{2pi i/3).
In general if K is a set of algebraic numbers (roots of polynomials with integer coefficients) satisfying 1, every non-zero element in K having a multiplicative inverse, and a condition saying that K is 'not very large compared to
'
[I can explain this better to you if you know about bases
and dimension] we say that K is a number field.The subset OK of K of all elements of K which are roots of polynomials with integer coefficient and leading coefficient 1, is called the ring of integers of K.
Tell me if you can understand what I wrote so far.
We will then continue by defining the Eisenstein primes and showing uniqueness of factorization
WARNING: Not all rings of integers of number fields have unique factorization. Lame 'proved' FLT (~1847 ?) assuming that they have.
Example: Let z = i sqrt 5. The set of all numbers of the form a + bz where a,b are rationals is a number field. Its ring of integers is the sets of all numbers A + Bz where A,B are integers. 2 , 3 , 1 + z , 1 - z are irreducibles (see next post) but 2.3 = 6 = (1 + z)(1 - z)
If this is an olympiad type question there must be a more 'elementary' way to do it (i.e. not using the Eisenstein integers). I might try it later.
Demetres
| Posted on Saturday, 14 June, 2003 - 11:49 am: |
You might like to note that numbers of the form a+bi where a and b are integers and i2 =-1 are sometimes known as Gaussian integers.
Vicky
| Posted on Saturday, 14 June, 2003 - 11:50 am: |
Hmm, Demetres seems to have some magical power predicting who is going to write the next post. [Edit: except it has been spoilt by Vicky's post 1 minute before mine]
OK, Let K be a number field, and OK its ring of integers.
The units are those elements of OK having a multiplicative inverse in OK .
Two numbers p,q in OK are said to be associate if p=(unit)*q.
We say a is a factor of b if there is an element c of OK such that ca=b.
We say a number a in OK is irreducible if its only factors are units and the associates of a. A number p is prime if, whenever p divides ab, then either p divides a or p divides b.
A prime is an irreducible, but the converse is not true for most number fields K.
The crucial point in my proof using Eisenstein integers is to establish that
for some integers a,b. From there on, there are 8 cases to check (remembering that x-y=c2 for some integer c).
The elementary way to do this probably need you to prove the fact that (x2 +xy+y2 ) being a square necessarily means that it is of the form (a2 +ab+b2 )2 , some
.Kerwin
| Posted on Saturday, 14 June, 2003 - 01:13 pm: |
What is going to be written in the next post rather than who is going to write. Unfortunately you were a bit slow. [My mistake though. I was thinking if I should mention the Gaussian integers or not !]
Demetres
| Posted on Saturday, 14 June, 2003 - 05:16 pm: |
Ok, I'm working through Demetres post at 10:17am.
I have checked addition, subtraction, multiplication properties.
I have proved that a.b=0 then either a or b = 0.
For the function f and its rational root x = p/q, (p,q)=1:
Therefore, pn /q must be an integer, but HCF(p,q)=1 so q = 1 hence x is an integer.
For, Eisenstein integers a+bw, are a and b always integers? You state that for a+bw +cw2 that a,b,c are integers.
Assuming that a,b are integers, I get:
a polynomial x2 + nx + m, has a+bw as a root if:
(a+bw)2 + n(a+bw) + m = 0
a2 + b2 w2 + b(2a+n)w + na+m = 0
If we chose integer n such that 2a+n=b then, because w2 +w=-1:
a2 - b2 + na + m = 0.
We then chose integer m, such that the above is true.
Therefore, f = x2 + nx + m has a+bw as a root.
I think this is all okay so far (just the question of whether a+bw, a and b are integers. I suppose my proof above relies quite heavily on that)
I think i followed the stuff on rings. I'm going to have something to eat now, and then I will look at establishing the crucial point of Kerwin's proof.
Thanks everybody,
Peter
| Posted on Saturday, 14 June, 2003 - 07:30 pm: |
How do "the conditions of the problem ensure that the factors x - y , x - wy , x - w2 y are pairwise coprime"?
Kerwin (or anyone), what does the notation that you did in LA TE X mean, about x and y?
Thanks,
Peter
| Posted on Saturday, 14 June, 2003 - 07:37 pm: |
Everything fine. a,b are indeed integers. Can you see how to write a + bw+ cw2 (a,b,c integers) in the form A + Bw (A,B integers) ?
Unique factorization: We define the norm of a + bw to be N(a + bw) = |a + bw| (the modulus of a + bw regarded as a complex number).
Step 1: The ring of Eisenstein integers is Euclidean with norm N [This means that given Eisenstein integers x and y (y =/= 0), there are Eisenstein integers q and r such that x = qy + r and Nr < Ny
[Hint: The Eisenstein integers tesselate the complex plane into parallelograms. Take q to be the Eisenstein integer closer to y]
Step 2: Every Euclidan domain has a unique factorization into irreducibles
[Uniqueness means that if x = p1 ...pn = q1 ...qm then m = n and after reordering (if necessary) pi and qi are associates]
Proof: Ask for it when you are ready
Demetres
| Posted on Saturday, 14 June, 2003 - 07:42 pm: |
Ok suppose p (irreducible) divides both x - y and x - wy. Then it divides (1-w)y so it either divides 1-w or it divides y. [Assuming uniqueness of factorization]
Derive a contradiction.
[Similarly for other pairs of factors]
Demetres
| Posted on Saturday, 14 June, 2003 - 07:56 pm: |
I mean the ordered pair (x,y) is either (a2 -b2 , b(b-2a)) or (b2 -a2 , 2ab-b2 ). This just follows once you have the coprime condition, and use w=(w2 )2 .
Hmm, I lied - there are really only 4 cases to check - we can force b> 0, and b divides y.
Kerwin
| Posted on Saturday, 14 June, 2003 - 08:45 pm: |
Sorry, I don't get it. How does the coprime condition give (x,y) as either (a2 -b2 , b(b-2a)) or (b2 -a2 , 2ab-b2 )?
Demetres,
Irreducible p can't divide y, because y is prime. And so must divide (1-w), but cannot, hence coprime. (Why not? is 1-w a prime)
Should I be able to prove the x = qy + r division result?
Peter
[What I thought might be a straightforwardish problem has turned out a bit harder!]
| Posted on Sunday, 15 June, 2003 - 12:03 am: |
1. You need to explain why p is not y, and why 3 does not divide z is important (hint: (1-w)2 =-3w).
2. Once you get the pairwise coprime condition, we have that each factor (x-w j y) is in the form (unit)*square. The proof is just like
,
so it is ±(a+bw)2 - now expand and
equate.3. Yes, 1-w is a prime in the Eisenstein integers.
4. The x=qy+r result - divide as you would in
, and take the (or a)
nearest point. Think about the equilateral
triangle.Kerwin
| Posted on Sunday, 15 June, 2003 - 10:16 am: |
My mistake for the x = qy + r result. I meant: Take q to be the eisenstein integer closer to x/y (NOT y)
[This is similar to the Euclidean algorithm for the natural numbers where you take q = [x/y]
Demetres
| Posted on Sunday, 15 June, 2003 - 04:59 pm: |
z2 =(x-y)(x-wy)(x-w2 y)
1.
If an irreducible p divides both (x-y) and (x-wy), then p also divides (1-w)y.
So p either divides (1-w) or y.
P cannot divide y, since y is prime (are all normal primes eisentein primes?). Nor can p = y, since p divides z, but y does not.
P cannot divide (1-w) since (1-w) is prime. Therefore p = (1-w). P divides both (x-y) and (x-wy), and so p2 divides z2 . But p2 = -3w, and so 3 divides z2 .
Contradiction.
(x-y) and (x-wy) are coprime.
Was that ok?
I assume the other pairs can be done similarly.
2.
Because z2 =(x-y)(x-wy)(x-w2 y), each of (x-y),(x-wy),(x-w2 y) must be a perfect square.
So (x-wy) = (a+bw)2
(x-wy) = a2 + b2 w2 + 2abw
w2 = -w-1
(x-wy)= a2 - b2 - (b2 -2ab)
x = a2 -b2
y = b2 -2ab
This okay?
a=3, b=1 works of course, giving 8,7,13.
What are the four cases to check?
(Still working on the x = qy+r)
Thanks,
Peter
| Posted on Sunday, 15 June, 2003 - 05:57 pm: |
Not all primes in
are
Eisenstein prime, e.g. 3. The primes in will remain prime in
the Eisenstein integers if and only if it cannot be
expressed in the form (a2 +ab+b2 )
(which factorises as (a-bw)(a-bw2 ). So for
example, 7=(22 +2+12 ) is not an
Eisenstein prime - it factors as (2-w)(2-w2
).One can argue as follows:
p divides (x-y) and (x-wy), so:
(A) p divides y gives p divides x as well, so x and y has a nontrivial common factor in the
(the Eisenstein integers). Thus we
have
But x and y are coprime in
(otherwise y divides
z, contradiction). Hence we have (by Bezout's Theorem)
integers a,b such that ax+by=1. So 1=g p for some Einsenstein integer
g , which is impossible since
p is not a unit.(B) p divides (1-w ) - then we have p=(unit)*(1-w ), which gives (since p divides both x-y and x-w y) 3 divides z, contradiction.
Complex conjugation gives the corresponding result for the pair (x-y), (x-w 2 y). The remaining pair is similar - subtract and you get p divides w (1-w )y, but w is a unit, so p divides (1-w )y and exactly the same argument goes through.
By unique factorisation, we have x-y, x-w y, x-w 2 y are all in the form (unit)*square. In particular, we can write x-w y as ±(a+w b)2 (since the units are of the form ±w 2j , j=0,1,2).
The four cases are:-
b divides y, so b=1 or y (y prime). Now you have to consider the plus-or-minus that is introduced by the unit for each value of b. Work out the value of a, and hence x (and possibly z) to show there is only 1 solution.
Kerwin
| Posted on Sunday, 15 June, 2003 - 08:21 pm: |
x=a2 -b2 , y = b2 -2ab or
x=b2 -a2 , y = 2ab-b2
Case 1:
b = 1
x = a2 -1, y = 1-2a
x-y must be a square: x-y = (a+1)2 -3
The only squares that differ by 3 are 4,1. Therefore a = -3, 1. But y must be positive, so a = -3. a=-3, b=1. x=8, y=7, z=13
Case 2:
b=y
x = a2 - y2
1 = y - 2a
a = (y-1)/2
which is smaller than y, so x would be negative.
no solutions.
Case 3:
b=1
x = b2 -a2 , y = 2ab - b2
x would be negative. no solutions
Case 4:
b=y
x = y2 -a2 , y = 2ay - y2
y = 2a-1
I'm temporarily stuck at this point
Thank you for all your help so far,
Peter
| Posted on Sunday, 15 June, 2003 - 08:58 pm: |
Hint (in white): Prove that x-y=c2 for some integer c. Rearrange and get what values a can take.
| Posted on Sunday, 15 June, 2003 - 10:10 pm: |
How about:
x=y2 -a2 , y = 2a - 1.
x-y = y2 - a2 - (2a - 1) = 4a2 -4a + 1 - 2a + 1
=3a2 - 6a + 2 = c2
c2 =3(a2 -2a) + 2
All integers2 are congruent to 1 (mod 3), but c2 is congruent to 2 (mod 3). So there is no integer c. Hence Case 4: no solutions.
Therefore (8,7,13) is the only triple.
Thanks
Peter