Hexagonal Honeycombs

When bees build honeycombs, they do so in a pattern of tiled hexagons.  They create the borders of the hexagon with wax, leaving hexagonal holes that they can use to store honey, pollen, or eggs.

But have you ever wondered why bees use hexagons?  Why not use a simpler shape, like squares, triangles, or circles?

The quick answer is that the hexagon is the single tileable polygon that has the least perimeter for a given area.  This is important because bees have to spend a lot of energy to make the wax for the borders of each honeycomb cell.  Less perimeter means less wax, and less wax means less spent energy.

Let’s examine the math behind the claim that the hexagon is the single tileable polygon that has the least perimeter for a given area.  First of all, we must show that there are only three regular polygons that can be tiled: the triangle, the square, and the hexagon.  Secondly, we must show that out of those three polygons, the hexagon is the one with the least perimeter for a fixed area.

Tileable Regular Polygons

First of all, we need to show that there are only three regular polygons that can be tiled.  In all regular polygons with n sides, the interior angle θ is θ = ^{(n – 2)180°}/_n.  So for a triangle (the polygon with the least amount of sides possible), n = 3 and θ = ^{(3 – 2)180°}/₃ = 60°; for a square, n = 4 and θ = ^{(4 – 2)180°}/₄ = 90°;  for a pentagon, n = 5 and θ = ^{(5 – 2)180°}/₅ = 108°; for a hexagon, n = 6 and θ = ^{(6 – 2)180°}/₆ = 120°; for a heptagon, n = 7 and θ = ^{(7 – 2)180°}/₇ = 128⁴/₇°; for a octagon, n = 8 and θ = ^{(8 – 2)180°}/₈ = 135°; and so on.  We can see that the values of the interior angles of a regular polygon are greater than or equal to 60° (for the triangle) but less than 180° (which represents a straight line, because otherwise it won’t close to make a polygon) and so 60° ≤ θ < 180°.

However, in order for a regular polygon to be tileable, its interior angle must also divide evenly into 360°.  The largest factor of 360° is 360° ÷ 1 = 360°, which is too big to be an interior angle of a regular polygon.  The second largest factor of 360° is 360° ÷ 2 = 180°, which is also too big.  However, the third largest factor of 360° is 360° ÷ 3 = 120°, which is the interior angle of a regular hexagon; the fourth largest factor is 360° is 360° ÷ 4 = 90°, which is the interior angle of a square; the fifth largest factor of 360° is 360° ÷ 5 = 72°, which is not the interior angle of any regular polygon; and the sixth largest factor of 360° is 360° ÷ 6 = 60°, which is the interior angle of an equilateral triangle.  After this, the factors of 360° are less than 60°, which are too small to be an interior angle of any regular polygon.  So the triangle, square, and hexagon are the only regular polygons that can be tiled.

Least Perimeter

Secondly, we must show that out of the three tileable regular polygons of the triangle, square, and hexagon, the hexagon is the one with the least perimeter for a fixed area.  Consider a regular polygon of n sides inscribed in a circle with a radius of r.   The polygon can be divided into n triangular slices, and each of those slices can be bisected at each central angle, making 2n symmetrical right triangles with an angle of ^π/_n and a hypotenuse of r.  The two legs of each right triangle are then r sin (^π/_n) and r cos (^π/_n), which makes the area of one of those right triangles ½r²sin(^π/_n)cos(^π/_n), and making the area of the whole regular polygon 2n times this or A = nr²sin(^π/_n)cos (^π/_n).  Also, since the opposite leg is r sin (^π/_n), 2 times this would give the length of one side of the whole regular polygon, and n times that would give the perimeter of the whole regular polygon or P = 2nr sin (^π/_n).

Solving the area equation for r gives us

and substituting this into the perimeter equation gives us

which simplifies to P = 2√A·√n·√tan(^π/_n).

So for a triangle, n = 3 and P = 2√A·√3·√tan(^π/₃) = 2√(3√3)√A ≈ 4.559√A.  For a square, n = 4 and P = 2√A·√4·√tan(^π/₄) = 4√A.  And for a hexagon, n = 6 and P = 2√A·√6·√tan(^π/₆) = 2√(2√3)√A ≈ 3.722√A.

Shape	Perimeter
triangle	4.559·√A
square	4.000·√A
hexagon	3.722·√A

Therefore, the hexagon has the least perimeter for a fixed area.

Wax Width

We have shown that the hexagon is the single tileable polygon that has the least perimeter for any given area.  But in a honeycomb grid, the perimeter of each cell is actually a wax border with its own width that is shared by adjacent cells, and this may affect our assertion that the hexagon is the most efficient shape.  So to be thorough, we need to consider the wax to honey ratio for each tiled shape.  We will consider the potential candidates of the triangle, square, hexagon, and circle.

Triangular Honeycombs

Let’s say there is a type of bee called the Triangle Bee that builds its honeycombs with equilateral triangles.  The Triangle Bees make wax walls that have a width of w that will separate each honey cell with an area of A and sides of s, and by the nature of the triangular pattern, the wax walls will meet in hexagon shapes.  The wax to honey ratio for the whole honeycomb would then be the same as one individual triangular tile, as colored below.

The wax walls for one tile consist of 3 sixths of a hexagon and 3 rectangles, and so its area W would be W = 3·¹/₆·^3√3/₂w² + 3·½sw or W = ^3√3/₄w² + ³/₂sw.  Since the area of an equilateral triangle is A = ^√3/₄s², solving for s would give us s = ^{2√(3√3)√A}/₃, and substituting back into W would give us W = ^3√3/₄w² + ³/₂(^{2√(3√3)√A}/₃)w or W = ^3√3/₄w² + √(3√3)√A·w.  The wax to honey ratio for the Triangular Bee is then (^3√3/₄w² + √(3√3)√A·w) / A ≈ (1.299w² + 2.280√A·w) / A.

Square Honeycombs

Now let’s say there is a type of bee called the Square Bee that builds its honeycombs with squares.  The Square Bees make wax walls that have a width of w that will separate each honey cell with an area of A and sides of s, and by the nature of the square pattern, the wax walls will meet in square shapes.  The wax to honey ratio for the whole honeycomb would then be the same as one individual square tile, as colored below.

The wax walls for one tile consist of 4 quarters of a square and 4 rectangles, and so its area W would be W = 4·¼·w² + 4·½sw or W = w² + 2sw.  Since the area of a square is A = s², solving for s would give us s = √A, and substituting back into W would give us W = w² + 2√A·w.  The wax to honey ratio for the Square Bee is then (w² + 2√A·w) / A.

Hexagonal Honeycombs

Now let’s say there is a type of bee called the Hexagonal Bee that builds its honeycombs with hexagons (like regular bees).  The Hexagonal Bees make wax walls that have a width of w that will separate each honey cell with an area of A and sides of s, and by the nature of the hexagonal pattern, the wax walls will meet in triangular shapes.  The wax to honey ratio for the whole honeycomb would then be the same as one individual hexagonal tile, as colored below.

The wax walls for one tile consist of 6 thirds of an equilateral triangle and 6 rectangles, and so its area W would be W = 6·¹/₃·^√3/₄w² + 6·½sw or W = ^√3/₂w² + 3sw.  Since the area of a regular hexagon is A = ^3√3/₂s², solving for s would give us s = ^{√(2√3)√A}/₃, and substituting back into W would give us W = ^√3/₂w² + 3(^{√(2√3)√A}/₃)w or W = ^√3/₂w² + √(2√3)√A·w.  The wax to honey ratio for the Triangular Bee is then (^√3/₂w² + √(2√3)√A·w) / A ≈ (0.866w² + 1.861√A·w) / A.

Circular Honeycombs

Finally, let’s say there is a type of bee called the Circular Bee that builds its honeycombs with circles.  The Circular Bees make wax walls that have at least a width of w that will separate each circular honey cell with an area of A and a radius of r.  The wax to honey ratio for the whole honeycomb would then be the same as one individual hexagonal tile, as colored below.

The area of the wax walls for one tile would be equivalent to the whole hexagon minus the circle, and so its area would be W = 2√3(½w + r)² – A.  Since the area of a circle is A = πr², solving for r would give us r = ^√π√A/_π, and substituting back into W would give us W = 2√3(½w + ^√π√A/_π)² – A = 2√3(¼w² + ^√π√A/_πw + ^A/_π) – A = ^√3/₂w² + ^{2√3√π√A}/_πw + (^2√3/_π – 1)A.  The wax to honey ratio for the Circular Bee is then (^√3/₂w² + ^{2√3√π√A}/_πw + (^2√3/_π – 1)A) / A ≈ (0.866w² + 1.954√A·w + 0.103A) / A.

Summary

The wax to honey ratio with respect to wax width and area are summarized for each shape below:

Shape	Wax to Honey Ratio
triangle	(1.299w2 + 2.280√A·w + 0.000A) / A
square	(1.000w2 + 2.000√A·w + 0.000A) / A
circle	(0.866w2 + 1.954√A·w + 0.103A) / A
hexagon	(0.866w2 + 1.861√A·w + 0.000A) / A

Since both w and A must be positive, the shape with the smallest wax to honey ratio coefficients would have to have the least wax to honey ratio, which is the hexagon.  Therefore, the hexagon is the most efficient shape to use for building a honeycomb.

Real honeybees build honeycomb cells that are an average of 4.85 mm wide (http://www.bushfarms.com/beesnaturalcell.htm), which gives a honey area of 81.484 mm², and with wax walls that have an average thickness of 0.5 mm (http://keepingbee.org/bee-honeycomb/).  Using these values, we can use the formulas above to calculate the numerical wax to honey ratio for each shape:

Shape	Ratio
circle	21.357%
triangle	13.025%
square	11.385%
hexagon	10.575%

Which means that the average honeycomb (made up of hexagons) has a 10.575% wax to honey ratio.

Conclusion

There are generally two opposing trains of thought concerning the fact that all bees happen to use the most efficient shape to build their honeycombs.  Evolutionists attribute the bees’ efficiency to natural selection.  They would say that at some point there may have been bees that tried to make square or triangular honeycombs, but they were not as efficient as the bees that made hexagonal honeycombs and were eliminated by the rules of the survival of the fittest.  On the other hand, creationists attribute the bees’ efficiency to Intelligent Design.  They would say that the instinct to build hexagonal honeycombs was put there by a God who not only created but also upholds all the geometrical laws of the universe.

Unfortunately, there are a few problems with using the theory of natural selection to explain why bees make their honeycombs in a hexagonal pattern rather than some other pattern.  First of all, although we have mathematically proved that the hexagon is the most efficient shape for a honeycomb of a fixed area, the square is not that far behind, and the difference of efficiency would be too small for natural selection to take place.  In fact, given that a real honeycomb has hexagon widths that vary from 4.6 mm to 5.1 mm (http://www.bushfarms.com/beesnaturalcell.htm), which would make honey cell areas vary from 73.300 mm² and 90.101 mm², a high end honey area made up of squares is actually more efficient than a low end honey area made up of hexagons! (A square honeycomb with w = 0.5 mm and A = 90.101 mm² would have a wax to honey ratio of 10.812%, whereas a hexagonal honeycomb with w = 0.5 mm and A = 73.300 mm² would have a wax to honey ratio of 11.165%.  Note that this does not contradict our above assertion because the areas are not the same.)  According to evolutionary natural selection, a mutation of bees that make large square honey cells should eliminate bees that make small hexagonal honey cells, but this of course has not happened.  Which brings us to the second problem of using the theory of natural selection to explain why bees make hexagonal honeycombs: out of the millions of beekeepers worldwide, and over three thousand years of beekeeping, there is not one recorded instance of a mutated colony of bees trying to make a honeycomb with something other than a hexagonal pattern.  The theory of evolution relies on these mutations to take place, both now and in the past, but there is just no evidence for this in bees.

If the reason bees make their honeycombs in a hexagonal pattern rather than some other pattern is not because of natural selection, then it must be because of some innate instinct.  But where did that instinct come from?  The only plausible explanation is that it came from an Intelligent Designer.  Bees build their honeycombs in the efficient hexagonal pattern because of an instinct that was put there by the same God who created the geometrical laws of the universe.

Semiprimes

Between 1991 and 2007, RSA laboratories were awarding cash prizes to any individual who could factor any number from their published list of semiprimes known as RSA numbers.  The first cash prize of $1000 was given on April 1, 1991 to Arjen Lenstra for factoring RSA-100, a semiprime with 100 decimal digits (330 binary digits), and the largest cash prize of $20,000 was given on November 2, 2005 to Jens Franke for factoring RSA-640, a semiprime with 193 decimal digits (640 binary digits).  To date, the largest RSA number to be factored is RSA-220, a semiprime with 220 decimal digits (729 binary digits) on May 13, 2016, but unfortunately no cash prize was given since the challenge is now over.

A semiprime is the product of two prime numbers.  For example, 15 is a semiprime because it is the product of the two primes 3 and 5.  The RSA Challenge is to find the two prime factors when given just the semiprime.  There are several ways to do this, but all of them are time consuming for large numbers.

Factoring Methods

For example, let’s say you wanted to find the two prime factors of the semiprime 91.  One way would be to divide 91 by each prime number between 1 and the square root of 91 until you reach one that divides it evenly.  So in this case, 91 ÷ 2 = 45 r 1 (no), 91 ÷ 3 = 30 r 1 (no), 91 ÷ 5 = 18 r 1 (no), 91 ÷ 7 = 13 r 0 (yes!), so 91 = 7 x 13.  (This method can be made to go somewhat faster by using divisibility rules.)

Another way would be to subtract a perfect prime square and see if the difference is also divisible by that squared number.  This is because if you call the semiprime n and the two factors p and p + d, n = p(p + d) or n = p² + pd or n – p² = pd.  So to factor 91, (91 – 2²) ÷ 2 = 43 r 1 (no), (91 – 3²) ÷ 3 = 27 r 1 (no), (91 – 5²) ÷ 5 = 13 r 1 (no), (91 – 7²) ÷ 7 = 6 r 0 (yes!), so 91 is divisible by 7.

One more way to factor a semiprime would be to add a perfect square and see if the sum is also a perfect square (assuming the semiprime is odd).  This is because if you call the semiprime n and the two factors p and q, and let u = ½(p + q) and v = ½(q – p), then u – v = ½(p + q) – ½(q – p) = ½p + ½q – ½q + ½p = p and u + v = ½(p + q) + ½(q – p) = ½p + ½q + ½q – ½p = q, which means n = pq = (u – v)(u + v) = u² – v², or n + v² = u².  So to factor 91, 91 + 1² = 92 (not a square), 91 + 2² = 95 (not a square), 91 + 3² = 100 = 10² (a square!), so the two factors of 91 are 10 – 3 and 10 + 3, or 7 and 13.  (This method can be made to go somewhat faster by filtering out sums whose last digit cannot possibly be a square number, which include 2, 3, 7, and 8.)

Computer Encryptions

As mentioned earlier, all the methods for factoring a large semiprime are time consuming, even for a computer, because they all use some variation of brute force or trial and error.  Computer programs rely on this fact with public and private key encryptions.  In a computer encryption, each user is given a public key (a large semiprime typically 1024 or 2048 binary digits long) that is publicly available for others to use to encode a message.  The message can then be decoded only by the private key (the two factors of the semiprime) that is known only by the receiver.  The RSA Challenge (hopefully) proved that this method of encryption is safe, because even after over 25 years nobody come even close to factoring RSA-1024.

Unfortunately, just like World War 2 Germany, public and private key computer encryptions are fighting a two-front war.  On the one front is mathematics – someone in the future may be clever enough to think of a more efficient way to factor large semiprimes.  On the other front is technology – someone in the future may develop a computer fast enough to use a brute force method to be able to factor large semiprimes.

Either way, the first person who can successfully factor large semiprimes, whether it is by a mathematical or technological breakthrough, would have the power to hack into anybody’s computer and steal their identity, including their bank account and credit card information, which presents an interesting hypothetical dilemma.  If this were to happen, will he or she use it for good or for evil? If for good, will he or she give large companies sufficient warning to find a new computer encryption method?  In the time in between, will he or she be kidnapped by the bad guys and forced to hack into computers for them?  Sounds like a Hollywood movie in the making!

At any rate, like all two-front wars it will only be a matter of time before the middle man will be defeated.  At some point, public and private key computer encryptions will become obsolete. Already on the technology front quantum computer processors are being developed where if they work they could factor large semiprimes almost instantaneously.  It’s time for a new encryption method!

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 = -⁸/₉).