Sunday, May 29, 2005

Fermat's Last Theorem: n = 3: a2 + 3b2

The essence of Euler's proof for Fermat's Last Theorem, n = 3, is realizing the properties of values that can be represented by the formula: a2 + 3b2.

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.



Tony Baker said...

There is an alternative to prove the lemma

If x is a factor of a^2 + 3b^2 then x is a factor of 1 + 3c^2 where c=b*d where d*a = 1 (mod x)

Let t be the largest natural number smaller than the square root of x

Let f_j be the remainder when dividing j*c by x, there is one j (from 1 to t) such that f_j is smaller than or equal t

So x is a factor of y = 3*f_j^2 + j^2 and 0 < y < 4x

There are there cases

(1) y = 2x this cannot happen since a square is only = 0 or 1 mod 4
(2) y = 3x then 3 must a divisor of j and so x = f_j^2 + 3(j/3)^2
(3) y = x and so x = j^2 + 3*f_j^2


Bernhard Kirchlechner said...

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².

Lu said...

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.

Larry Freeman said...

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.



Lu said...

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.

Larry Freeman said...

Hi Luigi,

You are correct. The step is not needed. I've updated the proof.

Thanks very much for noticing that. :-)



Xavier Onassis said...

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.

Larry Freeman said...

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.


Scouse Rob said...

I think in step (6):

x(m^2 ± 2mc + 3n^2x ± 6nd)

Should be:

x(m^2x ± 2mc + 3n^2x ± 6nd)


Scouse Rob said...

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:



Scouse Rob said...


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?



Larry Freeman said...

Hi Scouse Rob,

Step #5 was very unclear. I've cleaned it up so hopefully, step #5 is now clear.



havash said...

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?

M.V.V.Murthy said...

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.

joe marriott said...

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?

joe marriott said...

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?

Samsung Engineer said...

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