MaBloWriMo 8: definition of s and mod

I was a little unsatisfied with my proof yesterday since I don’t think I did a very good job explaining how $\pmod {M_n}$ enters into things. When sinuheancelmo asked a question which seemed to show confusion on exactly that point, I figured it would be worth spending a post to clarify things.

The main issue is that there are two slightly different ways we could have defined the sequence of numbers $s_n$ , and you will see both definitions in the literature. Here is Method 1:

$s_0 = 4$ .
$s_n = s_{n-1}^2 - 2$ .
$M_n$ is prime iff $s_{n-2} = 0 \pmod {M_n}$ .

And Method 2:

$s_0 = 4$ .
$s_n = (s_{n-1}^2 - 2) \bmod{M_n}$ .
$M_n$ is prime iff $s_{n-2} = 0$ .

Do you see the difference? In Method 1, the $s_n$ are defined without ever taking the remainder $\pmod {M_n}$ . So the $s_n$ will just keep getting bigger and bigger. Then we define the test by saying that $M_n$ is prime if $s_{n-2}$ is divisible by $M_n$ , that is, if $s_{n-2} = 0 \pmod{M_n}$ . In Method 2, on the other hand, we build $\bmod {M_n}$ into the definition of the $s_n$ , so they never get larger than $M_n$ . Then as the final test we can just require that $s_{n-2}$ is actually equal to zero.

In other words, the only difference between the two methods is how often we compute the remainder $\pmod {M_n}$ : once at the very end (method 1), or continuously as we go along (method 2). Method 1 is mathematically simpler, but you would never actually implement the test that way, since the $s_n$ get astronomically large. Method 2 corresponds to what you would actually implement, but it’s slightly more annoying to deal with all those $\pmod {M_n}$ ’s when proving things about it.

The two methods are mathematically equivalent, because taking remainders “commutes with addition and multiplication”, that is,

$(a + b) \bmod k \equiv (a \bmod k + b \bmod k) \pmod k$

(thought question: why can’t we just say $(a + b) \bmod k = a \bmod k + b \bmod k$ ?) and similarly for multiplication. That is, it doesn’t matter whether you take the remainder before or after adding or multiplying. Since the definition of $s_n$ only involves multiplying and adding (well, subtracting, but that’s just adding a negative number), we are justified in either taking the remainder as we go along or waiting until the very end—we will get the same result in either case.

Because I originally defined the $s_n$ according to Method 2, I had to carefully state the theorem from yesterday in terms of the remainder $\pmod {M_n}$ , and wave my hands about mod commuting with addition and multiplication. If we instead define $s_n$ according to Method 1, then the statement of the theorem and its proof do not have to mention $M_n$ at all: we just say

$s_m = \omega^{2^m} + \overline{\omega}^{2^m}$

and prove it by induction, in the same way that we did yesterday, but without the handwaving about taking remainders. In other words, what $\omega^{2^m} + \overline{\omega}^{2^m}$ actually gives us is the $s_m$ defined according to Method 1. If we build $\pmod{M_n}$ into the definition of the $s_m$ , then the theorem has to take this into account.

I think from now on we will just use the Method 1 definition of $s_n$ in the proof, but keep in mind that to actually implement it you would want to use Method 2.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →