In today's blog, I will present a lemma that illustrates one of the surprising properties of the above formula.
This blog will continue the details of the proof that was begun in a previous blog.
Lemma: If gcd(a,b)=1, then every odd factor of a2 + 3b2 has this same form.
In other words, for every odd factor of a2 + 3b2, there exists c,d such that the odd factor = c2 +3d2
(1) Let x be a positive, odd factor of a2 + 3b2
(2) Then, there exists a value f such that:
a2 + 3b2 = xf
(3) We can assume that x is greater than 1 (since if x = 1 it's only factor is itself and 1 = 12 + 3(0)2.)
(4) There exists integers m,n such that:
a = mx ± c
b = nx ± d
where c,d can be positive or negative.
(5) Now, we can assume that c,d have absolute values that are less than (1/2)x.
(a) From the Division Algorithm (see Theorem 1, here), we know that c is less than x.
(b) Assume that c ≥ (1/2)x
(c) c' = x - c = -(c - x)
(d) a = mx + c = (m+1)x + c - x = (m+1)x - (x - c) = (m+1)x - c'
(e) abs(c') is less than (1/2)x since c' = x - c
(6) From step #4, we have:
a2 + 3b2 =
(mx ± c)2 + 3(nx ± d)2 =
m2x2 ± 2mxc + c2 + 3n2x2 ± 6nxd + 3d2 =
= x(m2x ± 2mc + 3n2x ± 6nd) + c2 + 3d2
(7) So x divides c2 + 3d2 since from step #1, since x is a factor of a2 + 3b2.
(8) So, there exists y such that:
c2 + 3d2 = xy
(9) Now from step #5 above, we have:
xy = c2 + 3d2 is less than [(1/2)x]2 + 3[(1/2)x]2 = (1/4)x2 + (3/4)x2 = x2.
(10) Now, we can conclude that y is less than x from:
(a) Since c2, d2 are nonnegative, it follows that xy is nonnegative.
(b) From step #9, xy is less than x2
(c) Since x is positive, the only way that this can be true is if y is less than x.
(11) We also know that c2 + 3d2 ≠ 0 because:
(a) Assume c2 + 3d2 = 0.
(b) Then c=0, d=0 since c2 and 3d2 are both nonnegative.
(c) But then: a = mx, b = nx and x divides both a,b.
(d) Which contradicts gcd(a,b)=1 so we reject our assumption.
(12) Let g = gcd(c,d). We know there exists C,D such that c = gC, d=gD, gcd(C,D)=1. [From the properties of greatest common denominators]
(13) Now we also know that g2 divides y because:
(a) xy =c2 +3d2 = (gC)2 + 3(gD)2 = g2(C2 + 3D2)
(b) Assume there is a prime p that divides g but doesn't divide y.
(c) Then p divides g and p divides x
(d) Then, there exists X,G where x = Xp, g = Gp
(e) And, p divides a and b since
a = mx + c = mpX + GpC = p(mX + GC)
b = nx + d = npX + GpD = p(nX + GD)
(f) But this is impossible since a,b are coprime.
(g) So, there is no prime p which divides g but does not divide y.
(h) Which proves that g divide y and further that g2 divides y
(14) Since g2 divides y, there exists z such that:
y = g2z
(15) Now, it follows that there exist C,D such that:
xz = C2 + 3D2 where gcd(C,D)=1
(a) xy = g2(C2 + 3D2) [from step #13a above]
(b) gcd(C,D) = 1 [from step #12 above]
(c) Then substituting z from step #14 gives us:
xz = C2 + 3D2
(16) Now we have enough to conclude that x is of the form p2 + 3q2
(a) Assume that x is not of this form.
(b) From step #15, we have xz = C2 + 3D2 where gcd(C,D)=1.
(c) Then there must exist w such that w divides z and w is not of the form p2 + 3q2 [See here
for the proof of this lemma]
(d) Now, w ≠ 1 since 1 = 12 + 3(0)2
(e) So, w is smaller than z [since w is greater than 1 and w divides z]
(f) But then w is less than x [since z is less than y (step #14, since y = g2z) and y is less than x (step #10)]
(g) But now, we have proven that the existence of x proves the existence of a smaller factor w which divides a smaller value of the same form.
(h) We can use the same argument to presuppose a value w' which is smaller than w and another value w'' which is smaller than w'. In other words, we have a contradiction by the method of infinite descent.
QED
18 comments:
Hi, nice blog.
Some remarks:
In (4) c = x - (a - mx) is a positive number smaller than x/2 if (a - mx) is between x/2 and x. Perhaps this should read c = (a - mx) - x and you have a = m'x + c' with the given prerequisites (and you can therefore omit the ±).
In (5) the second line should read x(m²x ± 2mc + 3n²x ± 6nd) + c² + 3d².
Dear Larry,
I know you are busy, but I want tu submit you another question about your FLT's proof. Let's look at your May, 29th 2005,s lemma.
Question 1: in step (14) you stated that C^2+3*D^2 is an odd number. But I cannot find any point where this statement is used.
Question 2: in step (13)-d you recall definitions of c and d numbers stated in steps (3) and (4). But in step (11) you redefined c and d numbers to make y and c^2+3*d^2 numbers odd.
Question 3: my 1 and 2 questions are joined: indeed if y is odd ==> C^2+3*D^2 is odd.
I know it's not easy to talk about a complex proof you wrote years ago, but I would to try..... :-)
Thants for reading.
Luigi
Hi Luigi,
Thanks for your question. I've modified the proof in hopes of making it easier to follow.
Answer to Question 1:
We are trying to show here that xz is an odd number of the form a^2+3b^2.
This is used in the last step. Since xz has this form and we assume that x doesn't have this form, then using step #16b we get into infinite descent.
Answer to Question 2 and Question 3:
I've modified the proof. I hope that it's clearer now. If it is not, let me know and I will provide more details.
I hope that this answers your questions.
Cheers,
-Larry
Hi Larry,
thanks for rearranging your proof.
Infinite descend comes, IMHO, from this:
GCD (a,b)=1; x is an odd factor of a^2+3*b^2; x hasn't the p^2+3*q^2 form (step 16-a).
GCD (C,D)=1 (step 13); w is an odd factor of C^2+3*D^2 [w divides z (step 16-b) and z divides C^2+3*D^2 (step 15)]; w hasn't the p^2+3*q^2 form (step 16-b).
w < x (step 16-d).
PS w is odd after the xz=C^2+3*D^2 relation and after the proper lemma that says:
"if C^2+3*D^2 has an odd factor (the x number) who hasn't the p^2+3*q^2 form, then the quotient factor (the z number) has an odd factor (the w number) who hasn't the p^2+3*q^2 form."
From this I say, IMHO, it's not necessary to show the C^2+3*D^2 number is odd, then it is not necessary to show the y number is odd, then it's not necessary the step 12 of your proof, in the whole. Am I right?
Thanks for reading. Luigi.
Hi Luigi,
You are correct. The step is not needed. I've updated the proof.
Thanks very much for noticing that. :-)
Cheers,
-Larry
Thanks for the blog, I am leaning a lot.
In step (4) you state, "Since x divides both a and b,..."
Trouble is, I don't see why x has to dive both a and b. If a is divisible by 3 then x could be 3.
Hi Xavier,
Thanks for your question.
The statement there is unclear. When I say that a divides a,b I mean only that we can apply the division algorithm.
For any integer, we can apply the division algorithm and possibly get a remainder.
I'll update the wording to make this point clear.
I hope that answers your question.
-Larry
I think in step (6):
x(m^2 ± 2mc + 3n^2x ± 6nd)
Should be:
x(m^2x ± 2mc + 3n^2x ± 6nd)
Rob
Just been tying myself up in knots on step (5).
As stated
c ≥ (1/2)x (in 5b)
leads to:
abs(c')≤ (1/2)x (in 5f)
I think you have to use the fact that x is odd and so c≠(1/2)x to get the strict:
abs(c')<(1/2)x
Rob
Larry
I'm sorry but I'm having trouble getting the second loop of the infinite descent started again.
I think I understand that you need the following first statement (with w<x from the first loop, proved in step 16f):
Let w be a positive, odd factor of C^2 + 3D^2 [gcd(C,D)=1].
The only thing that I am having trouble with, is the proof that w, as constructed, is odd.
I think it is from the Step 16c lemma.
I this is so can you rewrite c to explicitly state that w is odd so don't get in such a mess next time?
Thanks
Rob
Hi Scouse Rob,
Step #5 was very unclear. I've cleaned it up so hopefully, step #5 is now clear.
Cheers,
-Larry
Hi, All prime factors of g dividing y seems to imply dividability of y by g and g square as trivial. But I don't see at all?! Neither for g nor g square even more.
What about the multiple prime factors? And Why can't they divide partially x too?
I have a doubt at step 16(c). How are we sure that z is not a prime and also not of the form (a^2+3b^2)? It is possible that x and z are both primes and not of the form (a^2+3b^2) but their product could still be of the form (a^2+3b^2). If z is a prime, the question of existence of a w such that 1<w<z does not arise and all further argument breaks down. Even the blog referred to at step 16(c) giving the proof of existence of w is based on the assumption that z can be factorized.
I have a question about a^2 + k*b^2.
if a^2 + k*b^2 is an odd number, and gcd(a,b)=1, are the factors of a^2+k*b^2 of the form c^2+kd^2?
I have a question about a^2 + k*b^2.
if a^2+k*b^2 is an odd number, and gcd(a,b)=1, are the factors of a^2+k*b^2 of the form c^2+kd^2?
how do you show there is one j (from 1 to t) such that f_j is smaller than or equal t, i think this is true but couldn't prove it
Why there are a,b as a 'integers' such as a=mx+c(-c) and b=nx+d(-d)? Is there any proof that a-c(+c)|m and b-d(+d)|n is correct?
What does the prime in level (5) means something? And Why does abs(c')<1/2x is a condradiction? I think it is a little ambiguous.
Someone please answer this one.
Post a Comment