Friday, November 04, 2005

Pell's Equation

Despite its name, Pell's Equation has nothing to do with the British mathematician John Pell. The problem was wrongly attributed to Pell by Leonard Euler in a very influencial work that Euler wrote when he was still in his 20s. Despite Euler's mistake (apparently, he had meant to cite Viscount William Brouncker), Pell's name stuck. Interestingly, according to Harold M. Edwards, there is a very good chance that Brouncker also wasn't involved with the problem. The work on the British side may have been done by John Wallis who cited Brouncker as an effort to gain favor with the viscount.

It was Pierre de Fermat who brought Europe's math community to focus on this equation in 1657 when he posed the problem as a challenge to the British mathematicians. Fermat was not the first to identify the problem. Diophantus studied one variant of Pell's equation and a famous problem by Archimedes known as the Cattle Problem can be stated in terms of Pell's equation. Great progress in solving Pell's equation were made by Indian mathematicians by Brahmagupta (born in 598 AD) and Bhascara Acharya (born in 1114 AD).

Pell's equation amounts to this:

Find all integer solutions for x,y where Ax2 + 1 = y2.

Interestingly, when this problem got passed on to the English, the part about "integers" was dropped and the British mathematicians quickly found a solution for rational solutions.

Here's the solution in terms of rational values:

Lemma: There are an infinite number of rational solutions to Ax2 + 1 = y2 where x,y are rational numbers.

(1) Let m = y-1, n = x. Then we know that: (y -1)/x = m/n and y-1 = (m/n)x and y = 1 + (m/n)x.

(2) So, Ax2 + 1 = [1 + (m/n)x]2 = 1 + 2(m/n)x + (m2/n2)x2

(3) Multiplying n2 to both sides gives us:

An2x2 + n2 = n2 + 2mnx + m2x2

And:
An2x2 = 2mnx + m2x2

And:
An2x2 - m2x2 = 2mnx

(4) Dividing x from both sides gives us:

An2x - m2x = 2mn = x(An2 - m2)

So that:
x = 2mn/(An2 - m2)

And:
y = 1 + (m/n)x = 1 + (m/n)(2mn/[An2 - m2]) =1 + 2m2/(An2 - m2) = (An2 - m2 + 2m2)/(An2 - m2) = (An2 + m2)/(An2 - m2)

QED

When Fermat saw the solution for rational values, he rejected it explaining that it was ridiculous to think that he would offer a problem as simple as this. He clarified that the problem is only interesting when the solution is for integers.

The British mathematicians at first responded that Fermat's new problem was artificial. They saw little justification for solving the problem specifically for whole numbers when the solution for rational values was valid. Later, an integer solution and a method for finding solutions was put forward without any proof that the method worked in all circumstances. Historically, Lord Brouncker is given credit for the solution.

The verification of the British method would have to wait over 100 years. It was the great mathematician Joseph-Louis Lagrange, using continued fractions, who showed that the British method worked in all circumstances. Go here to see how continued fractions can be used to provide a solution to Pell's equation.

References

Thursday, November 03, 2005

Dirichlet Integers

Today's blog continues the proof for Fermat's Last Theorem: n = 5. If you are interested in the history behind the proof, start here. If you are just interested in the mathematical details behind the proof, start here.

Today's blog continues on the problem of factoring a2 - 5b2 using quadratic integers of the form Z[(1 + √5)/2]. For those interested in understanding why we are not using Z[√5], please see here.

For purposes of this blog, when I say Dirichlet integers, I mean integers of the form:

Z[(1 + √
5)/2]

That is, integers of the form a + b(1 + √5)/2 where a,b are rational integers.

The basic idea behind the use of quadratic integers in a proof is the following:

(i) Quadratic integers are easier to factor than rational integers.

For example, using Z[(1 + √5)/2] we can factor a2 - 5b2 into (a - b5)(a + b5).

(ii) As long as a quadratic integer has unique factorization, it is possible to use quadratic integers to prove existence lemmas.

In the case of Fermat's Last Theorem: n=5, we will use Z[(1 + √5)/2] to prove:

If there exist two integers a,b such that:

(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2) is a fifth power.

Then there exists two integers c,d such that:

(i) a = c(c4 + 50c2d2 + 125d4)
(ii) b = 5d(c4 + 10c2d2 + 5d4)
(iii) gcd(c,d)=1
(iv) c,d have different parities
(v) 5 doesn't divide c
(vi) c,d are nonzero

Let's review the basics of Z[(1 + √5)/2]:

Definition

From a previous blog, we know that Z[(1 + √5)/2] is defined as:

a + b(1+√5)/2 [Since 5 ≡ 1 (mod 4), see here]

We also note that Dirichlet integers are charaterized by unique factorization. [See here]

Unique Factorization means that when we are reasoning about Dirichlet Integers, we can make use of the Division Algorithm, Euclid's Lemma, the Fundamental Theorem of Arithmetic, and Relatively Prime Divisors of N-Powers.

Norm Function

The norm is a mapping between Dirichlet integers and rational integers. This function is very useful for identifying units, primes, and in general, reasoning about Dirichlet integers. For review of norms and conjugates, please see here.

A norm for a quadratic integer is equal to the quadratic integer multiplied by its conjugate. So, the first step in figuring out the norm is to figure out the conjugate for a given Dirichlet integer.

Let's start with a Dirichlet integer based on integers a,b:

a + b(1+√5)/2

Now, this value is equivalent to:

[(2a + b) + b5]/2

So, the conjugate would be:

[(2a + b) - b5]/2

To simplify, we can set a' = (2a + b), b' = b. We note that a',b' will always have the same parity. In other words, they will both be odd or they both will be even.

Using a',b', the norm is:

Norm = (a' + b'5)/2*(a' - b'5)/2 = (a'2 - 5b'2)/4

Putting back in (2a+b) for a' and b for b', gives us:

Norm = (a'2 - 5b'2)/4 = [(2a+b)2 - 5(b)2]/4 =
(4a2 + 4ab + b2 - 5b2)/4 =
(4a2 + 4ab - b2)/4 =
a2 + ab - b2

Unit

A unit is any quadratic integer that divides 1. Units are needed in order to establish unique factorization with quadratic integers. You can review the ideas behind units and associates by starting here.

From a previous result, we know that a unit is also any quadratic integers whose norm is ± 1.

This means that we can determine the units for Dirichlet integers by solving the following equation:

(a'2 - 5b'2)/4 = 1

Which is the same as this:

a'2 - 5b'2 = 4

This is a difficult problem. To find the solution, I will now take a short detour to talk about Pell's Equation (another difficult problem posed by Pierre de Fermat). I will then use the solution to Pell's Equation to identify the units for Dirichlet integers.

Of course, we can simplify the problem by considering a'2 - 5b'2 = -4 which is clearly a=1, b =1.

It turns out that all Dirichlet units have the same form:

±[(1 + √5)/2]±n

Lemma 2: All Dirichlet units have the following form: ±[(1 + √5)/2]±n

(1) We know that (1 + √5)/2 is a unit since:

Norm( (1 + √5)/2 ) = [(1 + √5)/2][(1 - √5)/2] = (1 - 5)/4 = -4/4 = -1

Any value that has a norm = ±1 is a unit. [See here for proof]

(2) Assume that there existed a unit α that does not have the above form.

(3) Let ω = (1 + √5)/2

(4) So, we know that there exists some integer n such that:

α is greater than ωn and is less than ωn+1

(5) We know that ωn is a unit and ωn+1 is a unit since Norm(xn) = Norm(x)*Norm(x)*...*Norm(x) = (± 1)(± 1)*...*(± 1)

(6) Since a unit by definition divides 1, we know that ω-(n) is a unit since ωn is a unit.

(7) Likewise, we know that any unit divides any other unit, so we can divide all values by ωn which gives us:
1 is less than α which is less than ω

(8) But there is no such unit that is between 1 and ω

(a) Let's assume that there is was such a unit β

(b) So, there exists two rational integers: x,y such that β = (x + y5)/2 that is greater than 1 and less than ω

(c) And (x + y5) is greater than 2 and less than 2*ω which is less than 4.

(d) Now, since β is a unit, we know that Norm(β) = ± 1 = [(x + y5)/2][(x - y5)/2]

(e) This means that x = 1 or x = 2 since:

Case I: [(x + y5)/2][(x - y5)/2] = 1

Since (x + y5)/2 is greater than 1, then (x - y5)/2 is greater than 0 and less than 1.

So, x - y5 is greater than 0 and less than 2.

So (x + y5 + x - y5) is greater than 2 and less than 6.

So 2x is greater than 2 and less than 6

So x = 2.

Case II: [(x + y5)/2][(x - y5)/2] = -1

Since (x + y5)/2 is greater than 1, then (x - y5)/2 is greater than -1 and less than 0.

So, x - y5 is greater than -2 and less than 0.

So (x + y5 + x - y5) is greater than 0 and less than 4.

So 2x is greater than 0 and less than 4

So x = 1.

(f) But x ≠ 1 since:

(1 + y5)/2 is greater than 1 so y must be greater than 0 but then (1 + y5)/2 cannot be less than (1 + √5)/2

(g) And x ≠ 2 since:

(2 + y5)/2 is greater than 1 so y must be greater than 0.
(2 + y5)/2 is less than (1 + √5)/2, so y must be less than 1.

But there is no integer between 0 and 1 so we have reached a contradiction.

QED

Primes

Lemma 3: √5 is also a prime in Z[(1 + √5)/2]

(1) exists since = (0 + 25)/2

(2) is prime since Norm(5) = -5 [See Lemma 5 here]

QED

Lemma 4: 2 is a prime in Z[(1 + √5)/2]

See here for proof.

Wednesday, November 02, 2005

Fermat's Last Theorem: n = 5: Factoring a2 - 5b2

Today's blog continues the proof for Fermat's Last Theorem: n = 5. If you are interested in the history behind the proof, start here. If you are just interested in the mathematical details behind the proof, start here.

Today's blog continues the discusssion from here. The argument offered today comes from Harold M. Stark's An Introduction to Number Theory.

To establish the ideas behind the Key Lemmas, we will need to factor a2 - 5b2 into (a + b√5)(a - b√5). To do this, we will need unique factorization. For those who need a review of quadratic integers, start here.

Unfortunately, it turns out that Z[√5] is not characterized by unique factorization. (Note: Z[√5] notations describes the set of algebraic integers formed by a + b√5 where a,b are rational integers). To show this, I will introduce two lemmas:

Lemma 1: If a set Z[√d] is characterized by unique factorization, then 2 is not a prime.

(1) Assume that Z[√d] has unique factorization and 2 is a prime.

(2) d is either odd or even so either d or d-1 is divisible by 2.

(3) So, 2 divides (d)(d-1) = d2 - d = (d + √d)(d - √d) [Note, we can factor this up since we are assuming that Z[√d] has unique factorization]

(4) In Z[√d], 2 can't divide (d + √d) because 2 doesn't divide d. Likewise, 2 can't divide (d - √d)

(5) But this is a contradiction, since by Euclid's Lemma (one of the properties of unique factorization), 2 must divide either (d + √d) or (d - √d) if 2 divides (d + √d)(d - √d).

(6) So we can reject our assumption.

QED

Lemma 2: if d ≡ 1 (mod 4), then Z[√d] never has unique factorization.

(1) Suppose that 2 is not a prime in Z[√d]

(2) Then, there exists values: α, β such that:
2 = αβ

(3) Now, we note that Norm(2) = (2 - 0√d)(2 + √d) = 4 [See here for review of norms and conjugates]

(4) Since 2 = αβ, we also note that 4 = Norm(α)*Norm(β)

(5) Since 2 is not a prime and since it is not a unit, we can suppose that absolute(Norm(α)) is greater than 1 and absolute(Norm(β)) is greater than 1.

(6) This means that Norm(α) and Norm(β) must be equal to ­±2.

(7) Since α is in Z[√d], there must exist integers a,b such that α = a + b√d.

(8) So, Norm(α) = (a + b√d)(a - b√d) = a2 + b2d = ±2.

(9) Since d ≡ 1 (mod 4), we note that:

a2 + b2d ≡ a2 + b2(1) ≡ ±2 ≡2 (mod 4). [See here for a review of modular arithmetic]

(10) But this is impossible:

(odd) 2 ≡ (2u+1)2 ≡ 4u2 + 4u + 1 ≡ 1 (mod 4).

(even)2 ≡ (2u)2 ≡ 4u2 ≡ 0 (mod 4).

Case I: a is odd, b is odd: a2 - b2 ≡ 1 - 1 ≡ 0 (mod 4).

Case II: a is odd, b is even: a2 - b2 ≡ 1 - 0 ≡ 1 (mod 4).

Case III: a is even, b is odd: a2 - b2 ≡ 0 - 1 ≡ 3 (mod 4).

Case IV: a is even, b is even: a2 - b2 ≡ 0 - 0 ≡ 0 (mod 4).

QED

Luckily, there is a way out. From a previous result, we know that Z[(1 + √5)/2] has unique factorization.

So in my next blog, I will talk more about Z[(1 + √5)/2].

Tuesday, November 01, 2005

Fermat's Last Theorem: Proof for n = 5: Key Lemmas

Today's blog continues the proof for Fermat's Last Theorem: n = 5. If you are interested in the history behind the proof, start here. If you are just interested in the mathematical details behind the proof, start here.

Today's blog continues the proof on Fermat's Last Theorem: n=5 by offering two lemmas that are really the crucial idea behind the proof. Both lemmas rest on foundations of continued fractions and quadratic integers.

Lemma 1:

Given two integers a,b such that:

(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2) is a fifth power.

Then there exists two integers c,d such that:

(i) a = c(c4 + 50c2d2 + 125d4)
(ii) b = 5d(c4 + 10c2d2 + 5d4)
(iii) gcd(c,d)=1
(iv) c,d have different parities
(v) 5 doesn't divide c
(vi) 5 does divide d
(vii) c,d are nonzero

Proof:

(1) Assume that gcd(a + b5, a - b√5)= d which is greater than 1.

(2) Then there exists e,f such that:
de = a + b5
df = a - b5

(3) a + b5 + a - b5 = 2a = de + df = d(e + f)

(4) Likewise a + b5 - (a - b5) = 2b5 = d(e - f)

(5) Now d doesn't divide 5 since:

(a) 5 is a prime (see here).

(b) So if d divides it, it would have to = 5

(c) But d divides 2a (from #3)

(d) Which would mean 5 divides 2a which means 5 divides 4a2

(e) Which is impossible since 5 doesn't divide a.

(6) So d divides 2b.

(7) So d must divide 2 since it divides 2a and 2b but gcd(a,b)=1.

(8) Now 2 is prime so d=2. (See here)

(9) This means that 4 divides (a + b5)(a - b5) = a2 - 5b2

(10) But this is impossible since a,b have different parities:
(odd) - 5(even) = odd - even = odd
(even) - 5(odd) = even - odd = odd

So we reject our assumption.

(11) Since Z[(1 + 5)/2] has unique factorization (see here), we can conclude that a + b5 and a - b5 are fifth powers (see here ).

(12) This means that there exists m,n,t,u such that a + b5 = [(m + n5)/2]5[(t + u5)/2] where (t + u5)/2 is a unit.

(13) Now, if u = 0, then we reach our conclusion (see here). If u ≠ 0, we reach our conclusion (see here )

QED

Lemma 2:

Given two integers a,b such that:

(a) gcd(a,b)=1
(b) a,b are both odd
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2)/4 is a fifth power.

Then there exists two integers c,d such that:

(i) a = c(c4 + 50c2d2 + 125d4)/16
(ii) b = 5d(c4 + 10c2d2 + 5d4)/16
(iii) gcd(c,d)=1
(iv) c,d are both odd
(v) 5 doesn't divide c
(vi) 5 divides d
(vii) c,d are nonzero.

(1) Assume that gcd([a + b5]/2, [a - b√5]/2)= d which is greater than 1.

(2) Then there exists e,f such that:
de = (a + b5)/2
df = (a - b5)/2

(3) (a + b5)/2 + (a - b5)/2= a = de + df = d(e + f)

(4) Likewise (a + b5)/2 - (a - b5)/2 = b5 = d(e - f)

(5) Now d doesn't divide 5 since:

(a) 5 is a prime (see here).

(b) So if d divides it, it would have to = 5

(c) But d divides a (from #3)

(d) Which is impossible since 5 doesn't divide a.

(6) So d divides b.

(7) But this is impossible since gcd(a,b)=1.

So we reject our assumption.

(8) Since Z[(1 + 5)/2] has unique factorization (see here -- to be added later), we can conclude that (a + b5)/2 and (a - b5)/2 are fifth powers (see here -- to be added later).

(9) This means that there exists m,n,t,u such that (a + b5)/2 = [(m + n5)/2]5[(t + u5)/2] where (t + u5)/2 is a unit.

(13) Now, if u = 0, then we reach our conclusion (see here ). If u ≠ 0, we reach our conclusion (see here )

QED

To show the proof for these lemmas, it needs to be possible to factor a2 - 5b2 into (a - b√5)(a + b√5) [See here for details on unique factorization and the existence of 5 as a prime].

To avoid making Euler's mistake, we will need to make sure that Z[√5] or some variant such as Z[(1 + √5)/2] is characterized by unique factorization. More details can be found here.

Monday, October 31, 2005

Fermat's Last Theorem: n=5 : 5 doesn't divide z

For those interested in the history behind this proof, you may want to start here.

For those who would like to start at the beginning of this proof, start here.

The proof presented is based on two books: Harold M. Edward's Fermat's Last Theorem: A Genetic Introduction and Paulo Ribenboim's Fermat's Last Theorem for Amateurs.

Lemma: There are no integers x,y,z such that x5 + y5 = z5, xyz ≠ 0, gcd(x,y,z)=1, x,y are odd, z is even, and 5 divides x or y.

(1) Assume that x,y,z exist.

(2) For purposes of this proof, we will assume that 5 divides x (if it divides y, then we can make the exact same arguments replacing y for x)

(3) We know that there exists n,x' such that [since x is divisible by 5 from (#2)]:
x = 5nx' with n ≥ 1, gcd(x',5)=1
and 55nx'5 = y5 + z5

If we multiply 25 to both sides, we get:
(2)5(5)5nx'5 = 25(y5 + z5)

(4) from this we know that there are two integers p,q that have the following properties:
gcd(p,q)=1
p,q are both odd
(2)5(5)5nx'5 = 2p(p4 + 10p2q2 + 5q4)
p,q ≠ 0
(a) Let p = y + z, q = y - z

(b) p,q are both odd

p = odd + even = odd
q = odd - even = odd

(c) gcd(p,q)=1

Assume there is a prime f that divides both p,q such that p = fp', q = fq'. f is odd since p,q are odd.

f would divide y since p + q = f(p' + q') = y + z + y - z = 2y and since f is odd.

But f would also divide z since p - q = f(p' - q') = y + z - y + z = 2z and since f is odd.

But this is impossible since gcd(y,z)=1.

(d) (2)5(5)5nx'5 = 2p(p4 + 10p2q2 + 5q4) since:

(2)5(5)5nx'5 = 25(y5 + z5) =
(2y)5 + (2z)5 = (p+q)5 + (p-q)5 =
= 2p(p4 + 10p2q2 + 5q4) [By Lemma 1, here]

(e) p,q ≠ 0 since gcd(y,z)=1. [If y+z=0 or (y-z)=0, then y=z or y=-z which is not possible.]

(5) There exists an integer r that has these properties:
p=5r
gcd(q,r)=1
q,r are both odd
25m55nx'5 = 2*52r(q4 + 50q2 r2 + 125r4)
5 divides r
r ≠ 0
(a) 5 divides p since:

From step (#4d) and Euclid's Generalized Lemma, 5 divides 2p or 5 divides p4 + 10p2q2 + 5q4. If it divides 2p, then it divides p. Likewise, if 5 divides p4 + 10p2q2 + 5q4 then it must also divide p. [Details if needed are here] Either way, it divides p.

(b) Therefore, there exists a value r such that:
p = 5r

(c) gcd(r,q)=1 since gcd(p,q)=1 from step (#4c).

(d) We know r,q are both odd since:

odd divided by 5 = odd

(e) Finally, we note that applying r to step #4e gives us:
2p(p4 + 10p2q2 + 5q4)=
2(5r)[(5r)4 + 10(5r)2q2 + 5q4] =
2*5r*5(125r4 + 50r2q2 + q4) =
2*52r(q4 + 50q2 r2 + 125r4)

(f) 5 divides r

We know that 55n divides 2 * 52r(q4 + 50q2r2 + 125r4) from step (#4e and #5e).

So that 55n-2 divides 2 * r(q4 + 50q2r2 + 125r4)

Since n ≥ 1 (#2), 5n ≥ 5 which means 5n is greater than 2 so that we know that:
5 divides 2 * r(q4 + 50q2r2 + 125r4)

Now, we know that 5 doesn't divide q (since 5 divides p and gcd(p,q)=1 ) so that 5 cannot divide q4 + 50q2r2 + 125r4.

By Euclid's Generalized Lemma, since 5 divides 2 * r, it must divide r.

(g) r ≠ 0 since p ≠ 0 from step #4f.

(6) We know that there exists three integers a,b,t since:

(a) Let t' = q4 + 50q2 r2 + 125r4

(b) Let a' = q2 + 25r2

(c) Let b' = 10r2

(d) And we note that t' = a'2 - 5b'2. [By Lemma 2, here]

(e) Now a', b' are even

a' = (odd)2 + 25(odd)2 = odd + odd = even
b' is a multiple of 10.

(f) So, we know that there exists a,b such that:
a = (1/2)a'
b = (1/2)b'

(g) Let t = (1/4)t' = (1/4)(a'2 - 5b'2) = [(1/2)a']2 - 5[(1/2)b']2 = a - 5b2

(7) a,b,t have the following properties:

(a) gcd(a,b)=1

a = (1/2)(q2 + 25r2)
b = 5r2

Assume there exists a prime f that divides both a,b

There are three cases that we need to consider:
Case I: f = 2
Case II: f = 5
Case III: f divides both q,r

Case I isn't true since b is odd since r is odd.

Case II isn't true since 5 doesn't divide a. Multiplying 2 to both sides and using Euclid's Lemma, we know that if 5 divides a, then it would need to divide q2 + 25r2. But 5 doesn't divide q since 5 divides p and gcd(p,q)=1 so 5 cannot divide q2 + 25r2.

Case III isn't true since gcd(q,r)=1 from Step #4c.

So, they cannot have any common divisors.

(b) 5 doesn't divide a, 5 divides b

From step #6a we know that 5 divides b. From (a), we know that gcd(a,b)=1 so 5 can't divide a.

(c) a,b are both odd.

We already showed that b is odd so all we need to do is show that a is odd.

If a value is odd, there exists a value u such that: odd = 2u+1
(odd)2 = (2u + 1)2 = 4u2 + 4u + 1
So any (odd)2 ≡ 1 (mod 4) [start here if you need a review of modular arithmetic]
a'q2 + 25r21 + (1)(1) ≡ 2 (mod 4)

So, if a' ≡ 2 (mod 4), that there exists a value v such that a' - 2 = 4v and that (2a) -2 = 4v which means a - 1 = 2v and a = 2v + 1.

(d) (52r) * (t/4) = a fifth power since:

From #4e, we have:
25m55nx'5 = 2*52r(q4 + 50q2 r2 + 125r4)

Applying #5, we get
(2)5(5)5nx'5 = 2*52rt' = 2352rt

And dividing both sides by 25 gives us:
55nx'5 = (52rt)/4


(e) gcd(52r ,t/4) = 1 since:

Assume that there is a prime f that divides both. There are two cases that we need to consider:
Case I: f = 5
Case II: f divides r and t and f is odd (since r is odd)

Case I is false since 5 doesn't divide t'. t' = q4 + 50q2r2 + 125r4 but 5 can't divide t' since 5 doesn't divide q (see #6a).

Case II is false since f would need to divide q in order to divide t but gcd(r,q)=1 (#4c).

(f) t/4=(1/4)(a - 5b2 ) is a fifth power since:

#6d, #6e and Relatively Prime Divisors of n-powers.

(g) a,b are positive integers

We know this since q,r are nonzero integers (#3f,#4g) and #5 (since the square of a nonzero integer is a positive integer).

(8) Applying a lemma (see Lemma 2, here) , we can conclude that there exist c,d such that:

a = c(c4 + 50c2d2 + 125d4)/16
b = 5d(c4 + 10c2d2 + 5d4)/16
gcd(c,d)=1
c,d are both odd
5 doesn't divide c
5 divides d
c,d are nonzero.

(9) 53a =(1/4) (54d)[([c2 + 5d2]/2)2 - 5d4] since:

53a = (53)(5d)(c4 + 10c2d2 + 5d4)/16 = [(54d)/4][(c4 + 10c2d2 + 5d4)/4]

[(c2 + 5d2)/2]2 = (c4 + 10c2d2 + 25d4)/4

[(c2 + 5d2)/2]2 - 5d4 =
(c4 + 10c2d2 + 25d4)/4 - 20d4/4 = c4 + 10c2d2 + 5d4)/4

(10) [(c2 + 5d2)/2]2 - 5d4 ≡ 0 (mod 4)

(a) c2 ≡ 1 (mod 4) [since c is odd (#8) and step (#7c)]

(b) 5d2 ≡ (1)(1) ≡ 1 (mod 4) [since d is odd (#8) and step (#7c)]

(c) 5d4 = 5(d2)2 ≡ (1)(1) ≡ 1 (mod 4) [see above]

(d) [(c2 + 5d2)/2]2 - 5d4 ≡ [(1 + 1)/2][(1 + 1)/2] - 1 ≡ (1)(1) - 1 ≡ 0 (mod 4) [Note: for a review of modular arithmetic, go here]

(11) gcd([54d]/4 , [(c2 + 5d2)/2]2 - 5d4) = 1 since:

(a) Assume there is a prime f that divides both (54d)/4 and [(c2 + 5d2)/2]2 - 5d4.

(b) By Euclid's Lemma, f is either 5 or it divides d.

(c) f ≠ 5 since 5 doesn't divide c (#8) and therefore cannot divide [(c2 + 5d2)/2]2 - 5d4. [See here]

(d) f cannot divide d because if it did, then it would divide both d and [(c2 + 5d2)/2]2 - 5d4 which means that it would also divide c but this is impossible since gcd(c,d)=1 (#8).

(12) So, we know that (54d and (1/4)([(c2 + 5d2)/2]2 - 5d4) are fifth powers by Relatively Prime Divisors of n-powers theorem.

(13) Applying a lemma (see Lemma 2, here), we know that there exists c', d' such that:

(c2 + 5d2)/2 = c'(c'4 + 50c'2d'2 + 125d'4)

d2 = 5d'(c'4 + 10c'2d'2 + 5d'4)/16.

gcd(c',d') = 1

c',d' are both odd

5 doesn't divide c'

5
divides d'

c', d' ≠ 0

(14) We note that (58)d2 = (1/4)(59d')[([c'2 + 5d'2]/2)2 - 5(d'2)2] since:

(58)d2 = (59)d'(c'4 + 10c'2d'2 + 5d'4)/16 =
[(59)d'/4][(c'4 + 10c'2d'2 + 5d'4)/4]

(c'2 + 5d'2)2 = c'4 + 10c'2d'2 + 25d'2

(c'4 + 10c'2d'2 + 5d'4)/4 = [(c'2 + 5d'2)2 - 20d'2]/4 = [(c'2 + 5d'2)/2]2 - 5(d'2)2

(15) gcd((59)d' , (1/4)[(c'2 + 5d'2)/2]2 - 5(d'2)2 ) = 1 since:

(a) We can divide it up in this way since d' is odd, we know that 4 must divide the other value.

(b) Assume there is a prime f that divides both

(c) f = 5 or f divides d'

(c) f ≠ 5 since 5 doesn't divide c' (#13)

(d) f doesn't divide d' because if it did and it divided (1/4)[(c'2 + 5d'2)/2]2 - 5(d'2)2 then it would divide c' but gcd(c',d') = 1 (#13)

(16) We note that 58d2 is a fifth power since:

58d2 = (54d)2 and 54d is a fifth power (#12) [Since (x5)2 = (x2)5]

(17) So, we can conclude that 59d' and (1/4)[(c'2 + 5d'2)/2]2 - 5(d'2)2 are fifth powers by the Relatively Prime Divisors of N-Powers Theorem.

(18) Finally, we note that d' is ≥ 1 and less than d since:

(a) 25d'5 is less than 16d2 from step (#13)

(b) d' is greater than 0 (#13)

(c) Assume that d' ≥ d

(d) In this case, 25d'5 would be greater than 16d2 since d',d are integers, 25 is greater than 16 and d'5 is greater than d'2 which is greater or equal to d2.

(e) But this is not the case so we can reject our assumption at (c).

(19) But this means that we can repeat this process d times using the lemma stated above (see Lemma 2, here) and eventually get an integer d'' that is less than 1 and greater than 0 which is impossible.

QED