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.