Lattice Multiplication Method

In the Lattice Multiplication Method, a student is able to complete a multiplication problem of two large numbers by arranging numbers in a lattice grid.  For example, to multiply 48 x 12, the student would start out by creating a 2 x 2 lattice grid with the digits of 48 along the top as column headers, and the digits of 12 along the right side as row headers (Step 1).   The student would then multiply the digits in each column and row header and place each product in its corresponding position (using leading zeroes for single digit products), so in this case 4 x 1 = 04 (Step 2), 8 x 1 = 08 (Step 3), 4 x 2 = 08 (Step 4), and 8 x 2 = 16 (Step 5). 

Lattice Multiplication of 48 x 12

Finally, the student would add the digits along each diagonal, from the rightmost diagonal to the leftmost diagonal, and place each sum at the bottom left of each diagonal (carrying when necessary), so in this case 6 = 6 (Step 6), 8 + 1 + 8 = 17 which breaks down to 7 and a carried 1 (Step 7), 1 + 0 + 4 + 0 = 5 (Step 8), and 0 = 0 (Step 9).  The final answer can be determined by the right side column digits and the bottom row digits, in this case a final and correct answer of 576.  The Lattice Multiplication Method can also be extended to handle more digits by creating a larger lattice.

Lattice Multiplication Tutorial Video

The Lattice Multiplication Method is also known as Gelusia Multiplication, Sieve Multiplication, Shabakh, Venetian Squares, and the Chinese Lattice.  It is not known whether the method originated in Europe, the Middle East, or China, but it has been known since at least the 13^th century.

Validation

When it comes to multiplying two numbers of multiple digits, most people use the traditional Vertical Multiplication Method that is taught in most elementary schools.  For example, to multiply 48 x 12, the numbers are placed vertically, and the last digit of the top number is multiplied by the last digit of the second number to obtain 8 x 2 = 16, which is breaks down as 6 and a carried 1 (Step 1). 

Step 1	Step 2	Step 3	Step 4	Step 5
148         x 12               6	148         x 12            96	48         x 12            96            80	48         x 12            96          480	48         x 12            96     + 1480          576

Vertical Multiplication of 48 x 12

Then the first digit of the top number 4 is multiplied by the last digit of the second number 2 to obtain 4 x 2 = 8, plus the carried 1 makes 8 + 1 = 9, and so the first product is 96 (Step 2).  Then the last digit of the first number 8 is multiplied by the first digit of the second number 1 to obtain 8 x 1 = 8 and placed beside a place holder of 0 (Step 3).  Then the first digit of the first number 4 is multiplied by the first digit of the second number 1 to obtain 4 x 1 = 4, so the second product is 480 (Step 4).  The two products 96 and 480 are then added together to obtain the final answer of 96 + 480 = 576 (Step 5).

The Lattice Multiplication Method is simply a rearrangement of the same numbers in the Vertical Multiplication Method.  In the Lattice Multiplication Method, the digits of 48 and 12 are found in the top row and right column, and the digits in 96 and 480 are found inside the lattice (recall that the 9 was actually 8 and 1), and the digits of 576 are found in the left column and bottom row.

The Lattice Multiplication Method and the Vertical Multiplication Method both work for the same reason – the distributive property.  In both methods, the student multiplies 40 x 10, 40 x 2, 8 x 10, and 8 x 2 in some order and adds all the results together.  This is the algebraic equivalent of (40 + 8)(10 + 2) = 40·10 + 40·2 + 8·10 + 8·2 = 400 + 80 + 80 + 16 = 576, which is the same order as the popular FOIL method (first, outer, inner, last) taught in most algebra classes to show the distributive property.  In other words, the integrity of the multiplication is maintained because each digit of the first number is multiplied by each digit of the second number (with appropriate positioning to preserve place value) and then added all together.

Conclusion

The Lattice Multiplication Method is an algorithm for multiplying two large numbers by arranging numbers in a lattice grid.  Each digit of the two numbers are separated and placed as column and row headers, then the product of each column and row header is found and positioned inside the grid, and then the sum of each diagonal is found placed at the bottom left of each diagonal, and finally these sums can be read to obtain the solution.  Because each digit of the first number is multiplied by each digit of the second number (with appropriate positioning to preserve place value) and then added all together, it is a valid algorithm for multiplying two numbers.  The Lattice Multiplication Method is both organized and visually appealing, making it an ideal algorithm for multiplying two large numbers.

Japanese Multiplication Method

In the Japanese Multiplication Method, a student is able to complete a multiplication problem of two large numbers by merely drawing a few lines and counting the points of intersections.  For example, to multiply 21 x 23, the student first represents 21 by 2 diagonals lines that are drawn up and to the right followed by 1 diagonal line that is drawn in the same direction just underneath this, and then 23 by 2 diagonal lines that are drawn down and to the right followed by 3 diagonals lines that are drawn in the same direction just above this, so that the four groups of lines form a diamond shape. 

Japanese Multiplication of 21 x 23

The lines intersect in a total of 4 points on the left side of the diamond, a total of 8 points in the top and bottom sides of the diamond, and a total of 3 times on the right side of the diamond for a final and correct answer of 483.

The Japanese Multiplication Method can be extended to handle more digits by creating a larger diamond, and handle a digit of zero by drawing a different colored line.  In some cases, carrying is required in the final addition steps.

Japanese Multiplication Method Tutorial Video

Despite its name, the origin of the Japanese Multiplication Method is unknown.  The method is also known as Indian Multiplication and Chinese Stick Multiplication, but it is not known if it actually did originate from Japan, India, China, or elsewhere.

Validation

When it comes to multiplying two numbers of multiple digits, most people use the traditional vertical method that is taught in most elementary schools.  For example, to multiply 21 x 23, the numbers are placed vertically, and the last digit of the top number is multiplied by the last digit of the second number to obtain 1 x 3 = 3 (Step 1). 

Step 1	Step 2	Step 3	Step 4	Step 5
21         x 23               3	21         x 23            63	21         x 23            63            20	21         x 23            63          420	21         x 23            63      + 420          483

Vertical Multiplication of 21 x 23

Then the first digit of the top number 2 is multiplied by the last digit of the second number 3 to obtain 2 x 3 = 6, and so the first product is 63 (Step 2).  Then the last digit of the first number 1 is multiplied by the first digit of the second number 2 to obtain 1 x 2 = 2 and placed beside a place holder of 0 (Step 3).  Then the first digit of the first number 2 is multiplied by the first digit of the second number 2 to obtain 2 x 2 = 4, so the second product is 420 (Step 4).  The two products 63 and 420 are then added together to obtain the final answer of 63 + 420 = 483 (Step 5).

In summary, in the traditional vertical method a student first multiplies 1 x 3, then 20 x 3, then 1 x 20, then 20 x 20, and then adds all the results together.  In other words, when multiplying numbers with multiple digits, each digit of the first number is multiplied by each digit of the second number (with appropriate positioning or zeroes to preserve place value) and then added all together.  Algebraically, this can be expressed as (20 + 1)(20 + 3) = 3·1 + 20·3 + 1·20 + 20·20 = 3 + 60 + 20 + 400 = 483.  Tweaking the order a little bit gives the algebraic equivalent of (20 + 1)(20 + 3) = 20·20 + 20·3 + 1·20 + 1·3 = 400 + 60 + 20 + 3 = 483, which is the same order as the popular FOIL method (first, outer, inner, last) taught in most algebra classes. 

The same multiplication problem can be visualized with a table using Base Ten Blocks.  The 21 can be represented as 2 rod blocks and 1 unit block as row headers, and the 23 can be represented as 2 rod blocks and 3 unit blocks as column headers. 

Base Ten Block Multiplication of 21 x 23

The table would then be filled in by 4 square blocks (hundreds), a group of 6 rod blocks and another group of 2 rod blocks for a total of 8 rod blocks (tens), and 3 unit blocks (ones) for a final answer of 483.  Once again, each digit of the first number is multiplied by each digit of the second number (this time with appropriate shapes to preserve place value) and then added all together.

The Japanese Multiplication Method is simply a transformation of the Base Ten Block Table.  Instead of 4 square blocks there are 4 points of intersection on the left side of the diamond of lines, instead of a group of 6 rod blocks and a group of 2 rod blocks there are 6 points of intersection on the top side of the diamond of lines and 2 points of intersection on the bottom side of the diamond of lines, and instead of 3 unit blocks there are 3 points of intersection on the right side of the diamond of lines.  The integrity of the multiplication is maintained because each digit of the first number is multiplied by each digit of the second number (with appropriate positioning to preserve place value) and then added all together.

Because of its similarities with the FOIL method, it should be noted that the Japanese Multiplication Method can also be used to multiply polynomials.  The above Japanese Multiplication diagram that shows 21 x 23 = 483 can also be used to multiply (2x + 1)(2x + 3) and obtain the result 4x² + 8x + 3.  (The equation 21 x 23 = 483 is a specific example of (2x + 1)(2x + 3) = 4x² + 8x + 3 when x = 10.)

Evaluation

After watching the video and examining the above example, it is tempting to conclude that the Japanese Multiplication Method is the superior algorithm for multiplying two numbers.  After all, it just requires drawing a few lines and counting its intersections.  Unfortunately, the above example is a bit misleading because all of the numbers used have small digits (3 and under).  Here is an example of multiplying some numbers with larger digits, 69 x 78, using the Japanese Multiplication Method:

Japanese Multiplication of 69 x 78

In this example, a lot more lines have to be drawn, and a lot more points of intersection are formed.  Counting the points of intersection becomes time-consuming and carrying is required.  In this example, the Japanese Multiplication Method takes longer than the traditional vertical method of multiplication.

Still, the Japanese Multiplication Method is a great way to visualize the multiplication process, especially for numbers with smaller digits.

Conclusion

The Japanese Multiplication Method is an algorithm for multiplying two large numbers by representing both numbers by a group of lines that form a diamond pattern.  The number of points of intersection near each vertex of the diamond are then counted in a certain order to obtain the solution.  Because each digit of the first number is multiplied by each digit of the second number (with appropriate positioning to preserve place value) and then added all together, it is a valid algorithm for multiplying two numbers.  Unfortunately, the Japanese Multiplication Method is too time-consuming for multiplying numbers with larger digits, but remains a great visual aid for the multiplication process.

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