The Date of Easter

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 by 19 is 105, remainder 1).

Negative numbers

A subtle point is that the remainder is always a positive number in the range 0 to b−1, where b is the divisor (or modulus). 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, and some computer implementations of the modulus function do not behave in this way with negative numbers. Since in that case we are not interested in the quotient it is sufficient to check whether a negative remainder has been calculated and, if so, then 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.

Using a different range

Although the standard modulo operation gives a result in the range 0 to b−1, it is also possible to offset the result to a different range. In general, if the offset is c then the result will lie in the range c to c+b−1. Although there is no standard notation, this can be written as

a modc b

In mathematical terms values calculated with a different offset are congruent to one another.

This offset notation is a convenience and can easily be rewritten using a standard mod operator:

a modc b ≡ (a − c) mod b + c

About this page

This page is part of the oremus Almanac by Simon Kershaw.