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

QED

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

QED

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..... :-)

Luigi

Larry Freeman said...

Hi Luigi,

Thanks for your question. I've modified the proof in hopes of making it easier to follow.

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.

Cheers,

-Larry

Lu said...

Hi Larry,

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?

Larry Freeman said...

Hi Luigi,

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

Thanks very much for noticing that. :-)

Cheers,

-Larry

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,

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.

-Larry

Scouse Rob said...

I think in step (6):

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

Should be:

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

Rob

Scouse Rob said...

Just been tying myself up in knots on step (5).

As stated
c ≥ (1/2)x (in 5b)
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

Scouse Rob said...

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

Larry Freeman said...

Hi Scouse Rob,

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

Cheers,

-Larry

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

정진숙 said...

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?

정진숙 said...

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.