And now for something completely different

Take two large numbers, say 6387456347827 and 46983552814. What is the last digit of the sum of these two numbers? What is the last digit of their difference? And what about their product? To answer this question you only need to know the last digits of the two numbers, and the other digits do not really matter. You simply add, subtract or multiply the last digits of the numbers themselves and then look at the last digit of the result.

Now, consider the same two numbers. What remainder do you get when after adding both numbers you divide the result by 13? And what remainder do you get when you divide their difference by 13, and what when you divide their product? (Put away that calculator and try to figure this out using only your grey matter!)

The reason that this last problem seems a lot tougher than the first one, is that we are used to counting by tens. However, if you realize that taking the last digit of a number is really the same as taking the remainder after division by 10, both problems become strikingly similar, and we may use the same trick: instead of first adding, subtracting or multiplying and taking the remainder afterwards, we may take remainders first and only then add, subtract or multiply:

   6387456347827 / 13 =  491342795986 remainder 9
     46983552814 / 13 =    3614119447 remainder 3

   sum of the remainders         = 9 + 3 = 12
   difference of the remainders  = 9 - 3 =  6
   products of the remainders    = 9 x 3 = 27

Hence, the remainder of the sum after division by 13 is 12, the remainder of the difference is 6 and the remainder of the product is 27. (You may now use your calculator and check this, if you really must.)

Oops! We made a small mistake there. The remainder of the product after division by 13 cannot possibly be 27 as remainders are always smaller than the number you divide by. To get the true answer, you need to divide 27 again by 13 and take that remainder. The answer is 1. This is analogous to taking the last digit of the product of the last digits, instead of the product itself. The last digit of 6387456347827 times 46983552814 is not 28, but 8.

Modular arithmetic

Adding, subtracting or multiplying numbers and then taking remainders is called modular arithmetic. We say that the product of 9 and 3 modulo 13 equals 1, and we write

      9 x 3 = 1  (mod 13)

or sometimes

      9 x 3 = 1  (13)

Other examples are

      6387456347827 x 46983552814  =  9 x 3 =  1 (13)

      6 +  9 =   2  (13)
     21 -  5 =   3  (13)
     17 x 17 =   3  (13)
         123 =  97  (13)

An easy way to compute the third result is to use the trick above. Think of `4 times 4' instead of `17 times 17'. The last line simply says that 123 and 97 have the same remainder when divided by 13. This is obvious even without carrying out the actual division, for you may obtain 123 from 97 by adding 13 twice.

The same property may be used to work with negative numbers modulo 13. Simply add 13 a number of times until you end up with a positive number. For example:

         -6 =  7  (13)
        -60 =  5  (13)
	-13 =  0  (13)
     1 - 10 =  4  (13)

Modular arithmetic has much the same properties as ordinary arithmetic: it does not matter in which order you carry out a series of multiplications, multiplying by 0 yields 0, negating twice yields the original number, etc.

One word of warning: this arithmetic does not extend to division in the same way. There is such a thing as `modular division', but that is an entirely different cup of tea, and we won't need it here.

It may now become a bit clearer why we talk of a `modulus' of a CDS and why the mathematical definition mentions `differences modulo n'. Remember how we changed negative numbers in the difference table to positive numbers by adding the modulus? And how when constructing shifts we replaced the modulus by zero after incrementing the numbers? We were doing nothing more than using modular arithmetic before we knew its fancy name.

Modular arithmetic and semi-affine planes

97/01/01 - Kris Coolsaet