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.