How to Find the Next Largest Known Prime

The Electronic Frontier Foundation (EFF) is offering a $150,000 cash prize “to the first individual or group who discovers a prime number with at least 100,000,000 decimal digits” and a $250,000 cash prize “to the first individual or group who discovers a prime number with at least 1,000,000,000 decimal digits” (https://www.eff.org/awards/coop).  The current largest known prime number, 2^74,207,281 – 1, is just over 22 million digits long and was found on January 7, 2016 by mathematics professor Curtis Cooper using software from GIMPS (the Great International Mersenne Prime Search, http://www.mersenne.org/), an organization where private users can help calculations by donating computer processing time during off-hours via the internet.

A prime number is a number that is only divisible by 1 and itself, and a number that is not prime is called a composite number.  For example, the number 17 is a prime number because it is only divisible by 1 and 17 and no other numbers.  The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, and so on. 

In fact, back in ancient times Euclid proved that the list of prime numbers never ends.  If you suppose that there is a final prime number P, then there exists a number q which equals all the primes multiplied together plus one (q = p₁·p₂·p₃·…·P + 1).  Now, q cannot have a factor because if it did it would divide into q (by definition) and p₁·p₂·p₃·…·P (which has all the primes) and therefore also into 1 (since q = p₁·p₂·p₃·…·P + 1), which is impossible.  So q must be a prime number larger than P, but this contradicts the original assumption that P is the largest prime.  Therefore, there can be no final prime number P, which means the list of prime numbers never ends.  It also means that no matter how big the largest known prime is, there is always a bigger one waiting to be discovered.

There are also no known patterns for the distribution of prime numbers, but there are some tests.  The most basic way to test if a number n is a prime number is to use trial division, which divides the number n by all prime numbers p between 2 and √n.  If any p divides into the number n evenly, then the number n is not a prime number; otherwise if no p divides into the number n evenly, then the number n is a prime number.  For example, if we were to test n = 17 to be prime, we would divide 17 by all the prime numbers between 2 and √17 ≈ 4.1, or by 2 and by 3.  Since neither 2 nor 3 divide evenly into 17, 17 is a prime number. 

Unfortunately, trial division can become cumbersome very quickly with large numbers, because you have to know (and divide by) a list of all the prime numbers between 2 and √n.  Fortunately, there is a more efficient method called the Lucas-Lehmer test which can check whether a number is a Mersenne prime or not (and is also the method used by GIMPS).  A Mersenne prime, named after the French mathematician Marin Mersenne, is a prime number that can be expressed in the form of 2^p – 1.  For example, the number 7 is a Mersenne prime for p = 3, because 2³ – 1 = 7.  The first few Mersenne primes are 3 (p = 2), 7 (p = 3), 31 (p = 5), 127 (p = 7), 8191 (p = 13), and so on.  (It may be tempting to conclude that a Mersenne prime is formed whenever p is a prime number, but this is not true for the prime p = 11, because 2¹¹ – 1 = 2047 = 23·89 which is not prime.  It is true, however, that p must be a prime number for all Mersenne primes.)

The Lucas-Lehmer test uses the recursive sequence s₀ = 4 and s_n = s_n-1² – 2, and states that for all p > 2, s_p-2 is divisible by 2^p – 1 if and only if 2^p – 1 is a prime number.  For example, if we were to test p = 5, where 2^p – 1 = 2⁵ – 1 = 31, we would need to find s_p-2 = s_5-2 = s₃ and see if it is divisible by 31.  So s₀ = 4, s₁ = 4² – 2 = 14, s₂ = 14² – 2 = 194, and s₃ = 194² – 2 = 37634, which is divisible by 31, so 2⁵ – 1 = 31 is a prime number.  Since we are testing divisibility, the algorithm can be made even more efficient by using a modulus function, where s_n = (s_n-1² – 2) mod 2^p – 1, which means the Lucas-Lehmer test can be restated as s_p-2 ≡ 0 (mod 2^p – 1) if and only if 2^p – 1 is a prime number.  So to test p = 5 again, where 2^p – 1 = 31, the sequence would be s₀ = 4, s₁ = (4² – 2) mod 31 = 14, s₂ = (14² – 2) mod 31 = 194 mod 31 = 8, and s₃ = (8² – 2) mod 31 = 62 mod 31 = 0, so 2⁵ – 1 = 31 is a prime number.

Although the Lucas-Lehmer test is difficulty to prove (see here for the proof), it is very easy to program in a computer:

01	# Lucas-Lehmer Mersenne Prime Tester
02	# Python 2.7.3
03	# After running, type "M(p)" where p is the Mersenne Prime exponent in 2^p - 1.
04	#  For example, if you would like to test Mp = 2^7 - 1 = 127, type "M(7)".
05
06	# import python libraries
07	from time import time, strftime
08	import datetime
09
10	# M function
11	def M(p):
12	# make sure p > 2, a restriction for the Lucas-Lehmer algorithm
13	if p > 2:
14	# start timer
15	timestart = time()
16	# find Mp
17	Mp = 2 ** p - 1
18	# Lucas-Lehmer algorithm
19	s = 4
20	for x in range(0, p - 2):
21	s = (s * s - 2) % Mp
22	# display results
23	if s == 0:
24	print "2^" + str(p) + " - 1 is PRIME"
25	else:
26	print "2^" + str(p) + " - 1 is COMPOSITE"
27	#display elapsed time
28	timeelapsedint = round(time() - timestart, 2)
29	timeelapsedstr = str(datetime.timedelta(seconds = round(
30	timeelapsedint, 0)))
31	print "runtime: " + timeelapsedstr + " or " + str(
32	timeelapsedint) + " seconds."
33	else:
34	# p <= 2, so display a message to ask for p > 2
35	print "Please enter a number larger than 2."

Here’s what happens when you use this program to test a somewhat large Mersenne prime, 2^11,213 – 1, which has approximately 3,000 digits, on a dual-core 1.67 GHz processor (a mediocre-speed laptop for 2016):

>> M(11213) 2^11213 - 1 is PRIME runtime: 0:00:55 or 54.64 seconds.

So with less than 40 lines of code, you can use your computer to verify that a 3,000 digit number is prime in less than one minute!

Not bad, but this is still a far cry from the current record of 22 million digits, and an even further cry from the future cash-prize-awarding prime of 100 million digits.  In any case, finding the next largest prime number will require an educated guess, a fast computer (or more), and lots and lots of patience.

Proof for the Lucas-Lehmer Primality Test

The Lucas-Lehmer primality test states that for the recursive sequence s₀ = 4 and s_n = s_n-1² – 2, and for all p > 2, s_p-2 is divisible by 2^p – 1 if and only if 2^p – 1 is a prime number.  (The following is loosely based on the proof found here with some improvements.)

Definitions

s₀ = 4

Let a = ½s₀ = ½(4) = 2

Let b = a² – 1 = 2² – 1 = 3

Let u = a + √b

Let ū = a – √b

Then uū = (a + √b)(a – √b) = a² – b = a² – (a² – 1) = a² – a² + 1 = 1

Then s_n = u^{2^n} + ū^{2^n} by induction:

s₀ = u^{2^0} + ū^{2^0} = u¹ + ū¹ = u + ū = a + √b + a – √b = 2a = 2(½s₀) = s₀

Assuming s_n = u^{2^n} + ū^{2^n}:

s_n+1 = s_n² – 2

s_n+1 = (u^{2^n} + ū^{2^n})² – 2

s_n+1 = u^{2(2^n)} + 2u^{2^n}ū^{2^n} + ū^{2(2^n)} – 2

s_n+1 = u^{2^(n+1)} + 2(uū)^{2^n} + ū^{2^(n+1)} – 2

s_n+1 = u^{2^(n+1)} + 2(1)^{2^n} + ū^{2^(n+1)} – 2

s_n+1 = u^{2^(n+1)} + 2 + ū^{2^(n+1)} – 2

s_n+1 = u^{2^(n+1)} + ū^{2^(n+1)}

Proof of Sufficiency

Prove: If s_p-2 is divisible by 2^p – 1, then 2^p – 1 is a prime number.

Assume s_p-2 is divisible by 2^p – 1:

Let M = 2^p – 1

s_p–2 = kM

u^{2^(p-2)} + ū^{2^(p-2)} = kM

u^{2^(p-2)} = kM – ū^{2^(p-2)}

u^{2^(p-2)}u^{2^(p-2)} = kMu^{2^(p-2)} – ū^{2^(p-2)}u^{2^(p-2)}

(u^{2^(p-2)})² = kMu^{2^(p-2)} – (uū)^{2^(p-2)}

u^{2^(p-1)} = kMu^{2^(p-2)} – 1

Assume that 2^p – 1 is not a prime number:

Let q be the smallest factor of M = 2^p – 1

M ≡ 0 (mod q)

u^{2^(p-1)} ≡ k(0)u^{2^(p-2)} – 1 (mod q)

u^{2^(p-1)} ≡ -1 (mod q)

(u^{2^(p-1)})² ≡ (-1)² (mod q)

u^{2^p} ≡ 1 (mod q)

Since u^{2^(p-1)} ≠ 1, the order does not divide 2p – 1, so the order is 2^p

Let X = {n + m√b | n, m ε Z_q} and X* = {all elements of X except 0}

|X| = q² and |X*| = q² – 1 (as long as b = a² – 1 is not a perfect square)

u is in X*, and since the order of an element is at most the order of its size,

so 2^p ≤ q² – 1 < q²

Since q is the smallest factor of M, q² < M = 2^p – 1

But then 2^p < 2^p – 1 which is a contradiction

So 2^{p – 1} must be a prime number.

Proof of Necessity

Prove: If 2^p – 1 is a prime number, then s_p-2 is divisible by 2^p – 1.

Let M = 2^p – 1

Assume p is not a prime number

Then p has two factors m ≥ 2 and n ≥ 2 such that p = mn

But then 2^p – 1 = 2^mn – 1 which is divisible by 2^m – 1 and 2ⁿ – 1

This contradicts the assumption that 2^p – 1 is a prime number

So p must be a prime number

(-1)^(M-1)/2 ≡ -1 (mod M)

the exponent (M – 1)/2 = ½(2^p – 1 – 1) = ½(2^p – 2) = 2^p-1 – 1 must be odd

-1 to an odd exponent is -1

so (-1)^(M-1)/2 ≡ -1 (mod M)

2^(M-1)/2 ≡ 1 (mod M)

by Fermat’s Little Theorem, 2^p ≡ 2 (mod p), so 2^p – 2 = np

2^p – 2 must be even, and p (as a prime larger than 2) must be odd, so n = 2k and 2^p – 2 = 2kp

so the exponent (M – 1)/2 = ½(2^p – 1 – 1) = ½(2^p – 2) = kp

now 2^p ≡ 1 (mod 2^p – 1) or 2^p ≡ 1 (mod M)

so 2^(M-1)/2 = 2^kp = (2^p)^k ≡ 1^k (mod M) = 1 (mod M)

so 2^(M-1)/2 ≡ 1 (mod M)

3^(M-1)/2 ≡ -1 (mod M)

2²ⁿ⁺¹ – 1 ≡ 7 (mod 12) for all positive integers of n by induction:

2²⁽¹⁾⁺¹ – 1 = 2³ – 1 = 7 ≡ 7 (mod 12)

Assuming 2²ⁿ⁺¹ – 1 ≡ 7 (mod 12):

then 2²ⁿ⁺¹ ≡ 8 (mod 12)

2^{2(n + 1) +1} – 1 = 2^{2n + 3} – 1 = 2^{2n + 1 + 2} – 1 = 2^{2n + 1}2² – 1 ≡ 8(4) – 1 (mod 12) ≡ 7 (mod 12)

Since p is a prime larger than 2, p = 2n + 1 for all positive integers,

so M = 2^p – 1 = 2²ⁿ⁺¹ – 1 ≡ 7 (mod 12)

Since M ≡ 7 (mod 12), M = 12n + 7 for some integer n

By the law of quadratic reciprocity, (3 | 12n + 7)(12n + 7 | 3)

= (-1)^{½(3 – 1)½(12n + 7 – 1)} = (-1)^{6n + 3} = -1

Now, (12n + 7 | 3) = (3·4n + 3·2 + 1 | 3) ≡ (1 | 3) = 1

So (3 | 12n + 7) = -1

Or (3 | M) = -1, which means 3 is a quadratic nonresidue of M

So by Euler’s criterion, 3^(M-1)/2 ≡ -1 (mod M)

u^(M+1)/2 ≡ -1 (mod M)

u = a + √b = ^{(a + √b)2(a + 1)}/_{2(a + 1)} = ^{(a + 1 + √b)^2}/_{2(a + 1)}

because the numerator (a + √b)2(a + 1) = 2(a + 1)a + 2(a + 1)√b

= 2a² + 2a + 2(a + 1)√b = a² + a² + 2a + 1 – 1 + 2(a + 1)√b

= a² + 2a + 1 + 2(a + 1)√b + a² – 1 = (a + 1)² + 2(a + 1)√b + b = (a + 1 + √b)²

(recall that b = a² – 1)

so u^(M+1)/2 = [^{(a + 1 + √b)^2}/_{2(a + 1)}]^(M+1)/2 ≡ ^{2(a + 1)}/_{-2(a + 1)} (mod M) = -1 (mod M)

the numerator (a + 1 + √b)^2(M+1)/2 = (a + 1 + √b)^(M+1)

= (a + 1 + √b)(a + 1 + √b)^M ≡ -2(a + 1) (mod M)

using the binomial theorem in a finite field and prime exponent M,

(a + 1 + √b)^M ≡ (a + 1)^M + √b^M (mod M)

and using Fermat’s Little Theorem, (a + 1)^M ≡ a + 1 (mod M)

and √b^M = b^M/2 = b^{M/2 – ½ + ½} = b^{(M – 1)/2 + ½} = b^{(M – 1)/2}b^½ = (a² – 1)^{(M – 1)/2}b^½

= ((a – 1)(a + 1))^{(M – 1)/2}b^½ = (a – 1)^{(M – 1)/2}(a + 1)^{(M – 1)/2}b^½

since a = 2, (a – 1)^{(M – 1)/2} = (2 – 1)^{(M – 1)/2} = 1^{(M – 1)/2} ≡ 1 (mod M), and (a + 1)^{(M – 1)/2} = (2 + 1)^{(M – 1)/2} = 3^{(M – 1)/2} ≡ -1 (mod M)

so √b^M = (a – 1)^{(M – 1)/2}(a + 1)^{(M – 1)/2}b^½ ≡ (1)(-1)b½ (mod M) = -√b (mod M)

therefore, (a + 1 + √b)^M ≡ (a + 1 – √b) (mod M)

so (a + 1 + √b)^2(M+1)/2 = (a + 1 + √b)(a + 1 + √b)^M ≡ (a + 1 + √b)(a + 1 – √b) (mod M)

= (a + 1)² – b (mod M) = (a + 1)² – (a² – 1) (mod M) = a² + 2a + 1 – a² + 1 (mod M)

= 2a + 2 (mod M) = 2(a + 1) (mod M)

the denominator (2(a + 1))^(M+1)/2 = (2(a + 1))^{(M–1)/2 + 1} = (2(a + 1))^(M–1)/2(2(a + 1))

= 2^(M–1)/2(a + 1)^(M–1)/2(2(a + 1)) ≡ (1)(-1)(2(a + 1)) (mod M) = -2(a + 1) (mod M)

so u^(M+1)/2 ≡ -1 (mod M)

Therefore,

u^(M+1)/2 ≡ -1 (mod M)

u^{(M+1)/4+(M+1)/4} ≡ -1 (mod M)

u^(M+1)/4u^(M+1)/4 ≡ -1 (mod M)

u^(M+1)/4u^(M+1)/4ū^(M+1)/4 ≡ -ū^(M+1)/4 (mod M)

u^(M+1)/4(uū)^(M+1)/4 ≡ -ū^(M+1)/4 (mod M)

u^(M+1)/4(1)^(M+1)/4 ≡ -ū^(M+1)/4 (mod M)

u^(M+1)/4 ≡ -ū^(M+1)/4 (mod M)

u^(M+1)/4 + ū^(M+1)/4 ≡ 0 (mod M)

u^{(2^p–1+1)/4} + ū^{(2^p–1+1)/4} ≡ 0 (mod M)

u^{(2^p)/4} + ū^{(2^p)/4} ≡ 0 (mod M)

u^{2^(p–2)} + ū^{2^(p–2)} ≡ 0 (mod M)

s_p-2 ≡ 0 (mod M)

which means s_p-2 is divisible by 2^p – 1

Conclusion

We have proved the conditional (if s_p-2 is divisible by 2^p – 1, then 2^p – 1 is a prime number) and its converse (if 2^p – 1 is a prime number, then s_p-2 is divisible by 2^p – 1), which means the biconditional (s_p-2 is divisible by 2^p – 1 if and only if 2^p – 1 is a prime number) is also true.

Interesting Notes

Other s₀ values can be chosen, as long as the following criteria are met:

● b = a² – 1 is not a perfect square

● (a – 1)^{(M – 1)/2} ≡ 1 (mod M)

● (a + 1)^{(M – 1)/2} ≡ -1 (mod M)

The traditional value for s₀ is s₀ = 4 (a = 2, a – 1 = 1, a + 1 = 3, and b = 3), but other values that fit the above criteria are s₀ = 10 (a = 5, a – 1 = 4, a + 1 = 6, and b = 24) and s₀ = ²/₃ (a = ¹/₃, a – 1 = -²/₃, a + 1 = ⁴/₃, and b = -⁸/₉).

Fermat’s Last Theorem (n = 3 and n = 4)

History

After the French mathematician Pierre de Fermat died in the seventeenth century, a note written by Fermat was discovered in which he conjectured that there were no nonzero integer solutions to the equation xⁿ + yⁿ = zⁿ for n > 2.  This proposition became known as Fermat’s Last Theorem. 

Fermat also wrote that he had “discovered a truly marvelous demonstration of this proposition that this margin is too narrow to contain,” but no proof could be found in any of his other notes.  At the time, though, this seemed trivial, because surely some other mathematician would find a proof for it.  But as years turned to decades, and decades turned to centuries, no general proof could be found.

The proof for Fermat’s Last Theorem became a Holy Grail for mathematics.  Like the Holy Grail, some mathematicians spent their lives trying to find a proof but came back empty-handed.  And like the Holy Grail, other mathematicians doubted its existence.  Perhaps Fermat’s Last Theorem was incorrect and so couldn’t be proved (although no counter-example could be found, either).  Perhaps Fermat didn’t actually have a proof, or perhaps he thought he had a proof but then realized later that it was incorrect and so never published it.  On the other hand, perhaps Fermat had a proof but there have been no mathematicians as great as him since to re-create his proof.  In any event, by the beginning of the twentieth century finding a general proof for Fermat’s Last Theorem became sweeter than just mathematical notoriety, because an industrialist named Wolfskehl bequeathed a prize of 100,000 German Marks to the first mathematician who could prove it.

Fermat’s Last Theorem: The Holy Grail of Mathematics

In the meantime, specific proofs were found for Fermat’s Last Theorem.  A proof from Fermat himself was discovered for the specific case of n = 4 (that there were no nonzero integer solutions to the equation x⁴ + y⁴ = z⁴).  Euler proved Fermat’s Last Theorem for n = 3 in 1770, over a hundred years after Fermat’s death.  Dirichlet and Legendre proved Fermat’s Last Theorem for n = 5 in 1825, nearly two hundred years after Fermat’s death. 

More and more specific proofs were found for greater and greater exponents, but it was not until 1995, over three hundred years after Fermat’s death, that Wiles published a general proof that included all exponents greater than two.  His proof is over one hundred pages long, and uses modern methods and techniques not available to Fermat (and beyond the scope of this article), so most mathematicians agree that this is probably not the proof Fermat had in mind back in the seventeenth century (if he even had one).

Wiles

Difficulties

One of the reasons why Fermat’s Last Theorem is so difficult to prove is because it has to be true for a certain set of numbers but false for another set of numbers.  First of all, Fermat’s Last Theorem only applies for nonzero integer solutions.  However, integer solutions to xⁿ + yⁿ = zⁿ do exist for all exponents n as long as one of x, y, or z is equal to zero, for example, 1³ + 0³ = 1³ or 2⁴ + 0⁴ = 2⁴.

Secondly, Fermat’s Last Theorem also only applies for exponents greater than two.  Nonzero integer solutions to xⁿ + yⁿ = zⁿ do exist for n = 1 and n = 2.  When n = 1, the formula becomes x + y = z, which has infinitely many nonzero integer solutions, for example, 3 + 4 = 7 or 5 + 12 = 17.  When n = 2, the formula becomes x² + y² = z², which is the Pythagorean Theorem, and since it can be proved that all solutions to the Pythagorean Theorem are x = p² – q², y = 2pq, and y = p² + q² for any p and q (see here for a proof), an infinitely many combinations of nonzero integers p and q can be picked to generate nonzero integer solutions.  For example, if p = 2 and q = 1, then x = p² – q² = 2² – 1² = 3, y = 2pq = 2(2)(1) = 4, and z = p² + q² = 2² + 1² = 5, so x² + y² = z² is 3² + 4² = 5².  Or for another example, if p = 3 and q = 2, then x = p² – q² = 3² – 2² = 5, y = 2pq = 2(3)(2) = 12, and z = p² + q² = 3² + 2² = 13, so x² + y² = z² is 5² + 12² = 13².

Fermat’s Last Theorem for n = 3

Recall from above that Euler proved Fermat’s Last Theorem for n = 3 (that there are no nonzero integer solutions to x³ + y³ = z³) in 1770.  A few different ways to prove Fermat’s Last Theorem for n = 3 have been found, and a full proof, which is loosely based on the proof found on Freeman’s blog, can be found here. 

Summarizing the proof briefly, first assume that there are positive integer solutions to x³ + y³ = z³.  Then there must exist a cube in the form of 2p(p² + 3q²) where p and q are relatively prime and where the greatest common factor of 2p and p² + 3q² is 1 or 3.  In either case, you can use the fact that all odd factors of p² + 3q² must also have that same form (proof for that here) to prove that there exists smaller positive integers x’, y’, and z’ in which x’³ + y’³ = z’³.  Since we can apply the same argument infinitely to obtain smaller and smaller positive integers, there is a contradiction by the method of infinite descent, and so we reject our assumption that there are positive solutions to x³ + y³ = z³.  We can also reject that there are any negative solutions to x³ + y³ = z³ because the formula can be rearranged to an all positive integer solution still in the same form.  Since there are no positive or negative solutions to x³ + y³ = z³, there are no nonzero integer solutions to x³ + y³ = z³.

Fermat’s Last Theorem for n = 4

Also recall from above that a proof for n = 4 (that there are no nonzero integer solutions to x⁴ + y⁴ = z⁴) was given by Fermat himself.  The specific case for n = 4 is actually easier than proving the specific case for n = 3, because a fourth power is a square of a square, so a Pythagorean solution can be found twice in such a way to produce a contradiction once again by the method of infinite descent.  A full proof for Fermat’s Last Theorem for n = 4 can be found here.

Fermat’s Last Theorem for n ≥ 5

Proving Fermat’s Last Theorem for n = 3 proves Fermat’s Last Theorem for n for all multiples of 3, and likewise proving Fermat’s Last Theorem for n = 4 proves Fermat’s Last Theorem for n for all multiples of 4.  For example, to prove that there are no nonzero integer solutions for n for all multiples of 3, or n = 3m, one can simply express x^3m + y^3m = z^3m as (x^m)³ + (y^m)³ = (z^m)³, a special case for n = 3; and to prove that there are no nonzero integer solutions for n for all multiples of 4, or n = 4m, one can simply express x^4m + y^4m = z^4m as (x^m)⁴ + (y^m)⁴ = (z^m)⁴, a special case of n = 4.  So a general proof for Fermat’s Last Theorem only requires a proof for n of all prime numbers greater than two.

It is tempting to use the proofs for n = 3 or n = 4 and apply them to the proofs for higher exponents, but unfortunately both proofs for n = 3 and n = 4 exploit properties that are unique for its exponent.  The proof for n = 3 uses a unique property that all odd factors of p² + 3q² must also have that same form.  But using the same logic as the proof for n = 3 on n = 5, we would need all odd factors of p⁴ + 10p²q² + 5q⁴ to have the same form, but unfortunately this is simply not true, and the same can be said for higher exponents.  Furthermore, the proof for n = 4 uses the unique property that a fourth power is a square of a square, which is not true of any primes greater than two.  So a specific proof for any prime n ≥ 5 must use a completely different (and more difficult) approach altogether.

Conclusion

Even though Fermat’s Last Theorem was proved by Wiles in 1995, some mysteries remain.  Did Fermat really have a legitimate general proof for his theorem, or was he mistaken?  Will a general proof be found that is shorter or uses a traditional approach?  Perhaps it will take another three centuries to answer these questions.  If only Fermat’s margin was bigger!

Fermat’s Last Theorem (Proof for n = 4)

There are no nonzero integer solutions to x⁴ + y⁴ = z⁴

001	Assume x4 + y4 = z4, where x, y and z are nonzero integers.
002	Letting w = z2, we have x4 + y4 = w2.
003	Dividing out any common factors, there exists an X, Y, and W such that X4 + Y4 = W2 in which X, Y, and W are relatively prime.
004	Then (X2)2 + (Y2)2 = W2
005	Then there exists a Pythagorean solution for (X2)2 + (Y2)2 = W2, which is X2 = p2 – q2, Y2 = 2pq, and W = p2 + q2, where p, q and X are relatively prime.
006	Then there also exists a second Pythagorean solution for X2 = p2 – q2, which is X = m2 – n2, p = m2 + n2, and q = 2mn, where m and n are relatively prime.
007	Assume p and m are not relatively prime:
008	Then p = fP and m = fM
009	And n is also divisible by f since n2 = p – m2 = fP – (fM)2 = fP – f2M2 = f(P – fM2)
010	Then n and m have a common factor f.
011	But this contradicts that m and n are relatively prime.
012	So p and m are relatively prime.
013	Assume p and n are not relatively prime:
014	Then p = fP and n = fN
015	And m is also divisible by f since m2 = p + n2 = fP + (fN)2 = fP + f2N2 = f(P + fN2)
016	Then n and m have a common factor f.
017	But this contradicts that m and n are relatively prime.
018	So p and n are relatively prime.
019	Therefore, since m and n are relatively prime, and p and m are relatively prime, and p and n are relatively prime, that means p, m, and n are relatively prime.
020	Now  Y2 = 4pmn, because Y2 = 2pq = 2p(2mn) = 4pmn.
021	Since Y2 = 4pmn and p, m, and n are relatively prime, p, m, and n are squares, so p = w’2, m = x’2, and n = y’2
022	Substituting into p = m2 + n2, we have w’2 = (x’2)2 + (y’2)2, or x’4 + y’4 = w’2.
023	Now x’ < w since x’ is a factor of m which is a factor of q which (because W = p2 + q2) is less than W which a factor of w
024	And y’ < w since y’ is a factor of n which is a factor of q which (because W = p2 + q2) is also less than W which is a factor of w
025	And w’ < w since w’ is a factor of p which (because W = p2 + q2) is also less than W which is a factor of w
026	So there exists integers x’, y’, and w’ such that x’4 + y’4 = w’2 and 1 ≤ x’ < w, 1 ≤ y’ < w, and 1 ≤ w’ < w.
027	Therefore, if x4 + y4 = w2, there must exist other positive integers x’, y’, w’ such that 1 ≤ x’ < w, 1 ≤ y’ < w, and 1 < w’ < w in which x’4 + y’4 = w’2.
028	But we can use the same argument to prove the existence of more positive integers x”, y”, w” such that 1 ≤ x” < w’, 1 ≤ y” < w’, and 1 < w” < w’ in which x”4 + y”4 = w”2, and another x’”, y’”, w’”, and so on, so we have a contradiction by the method of infinite descent.
029	Therefore, there are no nonzero integer solutions to x4 + y4 = z4.

Q.E.D.