^{2}+ 3b

^{2}.

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 a

^{2}+ 3b

^{2}has this same form.

In other words, for every odd factor of a

^{2}+ 3b

^{2}, there exists

**c,d**such that the odd factor =

**c**

^{2}+3d^{2}(1) Let

**x**be a positive, odd factor of

**a**

^{2}+ 3b^{2}(2) Then, there exists a value

**f**such that:

**a**

^{2}+ 3b^{2}= xf(3) We can assume that x is greater than 1 (since if

**x = 1**it's only factor is itself and 1 = 1

^{2}+ 3(0)

^{2}.)

(4) There exists integers

**m,n**such that:

**a = mx ± c**

b = nx ± d

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:

a

^{2}+ 3b

^{2}=

(mx ± c)

^{2}+ 3(nx ± d)

^{2}=

**m**

= x(m

^{2}x^{2}± 2mxc + c^{2}+ 3n^{2}x^{2}± 6nxd + 3d^{2}== x(m

^{2}x ± 2mc + 3n^{2}x ± 6nd) + c^{2}+ 3d^{2}(7) So

**x**divides

**c**since from step #1, since x is a factor of a

^{2}+ 3d^{2}^{2}+ 3b

^{2}.

(8) So, there exists

**y**such that:

**c**

^{2}+ 3d^{2}= xy(9) Now from step #5 above, we have:

**xy = c**is less than

^{2}+ 3d^{2}**[(1/2)x]**.

^{2}+ 3[(1/2)x]^{2}= (1/4)x^{2}+ (3/4)x^{2}= x^{2}(10) Now, we can conclude that y is less than x from:

(a) Since c

^{2}, d

^{2}are nonnegative, it follows that xy is nonnegative.

(b) From step #9, xy is less than x

^{2}

(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

**c**because:

^{2}+ 3d^{2}≠ 0(a) Assume

**c**

^{2}+ 3d^{2}= 0.(b) Then

**c=0, d=0**since c

^{2}and 3d

^{2}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

**g**divides

^{2}**y**because:

(a)

**xy =c**

^{2}+3d^{2}= (gC)^{2}+ 3(gD)^{2}= g^{2}(C^{2}+ 3D^{2})(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)

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

**g**divides

^{2}**y**

(14) Since g

^{2}divides y, there exists z such that:

y = g

^{2}z

(15) Now, it follows that there exist C,D such that:

**xz = C**where

^{2}+ 3D^{2}**gcd(C,D)=1**

(a)

**xy =**

**g**[from step #13a above]

^{2}(C^{2}+ 3D^{2})(b) gcd(C,D) = 1 [from step #12 above]

(c) Then substituting z from step #14 gives us:

**xz = C**

^{2}+ 3D^{2}(16) Now we have enough to conclude that

**x**is of the form

**p**

^{2}+ 3q^{2}(a) Assume that

**x**is not of this form.

(b) From step #15, we have

**xz = C**where

^{2}+ 3D^{2}**gcd(C,D)=1**.

(c) Then there must exist

**w**such that

**w**divides

**z**and

**w**is not of the form

**p**[See here

^{2}+ 3q^{2}for the proof of this lemma]

(d) Now,

**w ≠ 1**since

**1 = 1**

^{2}+ 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 = g**) and y is less than x (step #10)]

^{2}z(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

## 19 comments:

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

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^2

x± 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