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.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, iteration, modular arithmetic, number theory and tagged , , , , , , , . Bookmark the permalink.