Modulo Arithmetic

Modulo arithmetic is concerned with the division of whole numbers (or integers) into a quotient and a remainder.

For example, 7 divided by 3 is 2 (the quotient), remainder 1. 12 divided by 3 is 4 remainder 0.

In this paper we refer to the quotient of two numbers, a and b as

a div b

and the remainder as

a mod b

To use the above examples, 7 div 3 is 2, and 7 mod 3 is 1.

For a more complicated example 1996 div 19 is 105, and 1996 mod 19 is 1 (because 1996 divided 19 is 105, remainder 1).

A subtle point is that the remainder is always a positive number. So -7 divided by 3 is -3, remainder 2 (rather than -2, remainder -1). This is important for the date of Easter because we must often calculate the remainder when dividing into a negative number. Since in that case we are not interested in the quotient it is sufficient to calculate the negative remainder and then simply add to it the number we were dividing by. So -11 mod 3 may be calculated as: -11 divided by 3 is -3, remainder -2, so the number required is -2 + 3 = 1.

Simon Kershaw <simon@oremus.org>
10 February 2004