Formal Foundations of Computer Science 1 -- 7.1.2 Modular Arithmetic

Go backward to 7.1.1 Basic Notions
Go up to 7.1 Equivalence Relations and Partitions
Go forward to 7.1.3 Another Construction of Number Domains

7.1.2 Modular Arithmetic

The domain of integer numbers introduced in Chapter Numbers has infinite size, i.e., there is no upper bound for an integer. However, computer processors can only operate with numbers of a maximum size determined by the length of a computer word on the corresponding architecture, e.g., a 64 bit architecture only supports 2⁶⁴ different numbers.

Apparently the question arises how to define the result of an operation whose value is outside the range that can be represented by such a word, e.g., the result of 2⁴⁰*2³⁰. While we may consider such an operation "illegal" (and raise a hardware interrupt), there is a more elegant solution provided by modular arithmetic: we define the result of every operation as the result of the unbounded integer operation modulo the number m of elements that can be represented by a computer word.

We start with a preliminary definition of modular arithmetic, which will later be replaced by a more suitable one.

Definition 104 (Modular Arithmetic, Direct Approach) Let m in Z_>0 and Z_m := {x in Z: 0 <= x < m}.

+_m: Z x Z -> Z_m

x +_m y := (x + y) mod m

-_m: Z x Z -> Z_m

x -_m y := (x - y) mod m

-_m: Z x Z -> Z_m

-_m x := (-x) mod m

*_m: Z x Z -> Z_m

x *_m y := (x * y) mod m

Example These tables describe arithmetic modulo 3 for a subset of Z:

+₃ -4 -3 -2 -1 0 1 2 3 4

-4 1 2 0 1 2 0 1 2 0

-3 2 0 1 2 0 1 2 0 1

-2 0 1 2 0 1 2 0 1 2

-1 1 2 0 1 2 0 1 2 0

0 2 0 1 2 0 1 2 0 1

1 0 1 2 0 1 2 0 1 2

2 1 2 0 1 2 0 1 2 0

3 2 0 1 2 0 1 2 0 1

4 0 1 2 0 1 2 0 1 2

*₃ -4 -3 -2 -1 0 1 2 3 4

-4 1 0 2 1 0 2 1 0 2

-3 0 0 0 0 0 0 0 0 0

-2 2 0 1 2 0 1 2 0 1

-1 1 0 2 1 0 2 1 0 2

0 0 0 0 0 0 0 0 0 0

1 2 0 1 2 0 1 2 0 1

2 1 0 2 1 0 2 1 0 2

3 0 0 0 0 0 0 0 0 0

4 2 0 1 2 0 1 2 0 1

In above definition, the arguments may be arbitrary integers while the result is one of m values. However, a little investigation of the function tables reveals that the same pattern of result values is repeated every m lines and every m columns. Consequently, it does not matter whether we compute with an argument a or with a+3 or with a-3 or with a+3i for any i in Z. We may therefore define the set of all values

[a]_m := {a+im: i in Z}

that cannot be distinguished from a by modular arithmetic modulo m. However, this definition is just a special case of the construction of equivalence classes, as we are going to elaborate now. This construction will provide us with a suitable domain for modular arithmetic.

First we define the relation that links two integers that "are the same" with respect to arithmetic modulo m.

Definition 105 (Modular Congruence) Two integers x and y are congruent (kongruent) modulo m if they have the same remainder when divided by m:

x = _m y : <=> (x mod m) = (y mod m).

Clearly = _m is an equivalence relation, for every m in Z_>0. The equivalence classes induced by this relation collect all the integers that cannot be distinguished by arithmetic modulo m.

Definition 106 (Residue Class) The residue class (Restklasse) of a modulo m is the set of all integer numbers that are congruent to a modulo m.

[a]_m := [a]_{= _m}.

It is easy to see that [a]_m = {a+im: i in Z} as was our original intuition. However, the new construction has the advantage that we may construct the quotient set of Z with respect to = _m, which gives a suitable domain for modular arithmetic.

Definition 107 (Modular Integer Numbers) The set of integers modulo m is the quotient set of Z with respect to congruence modulo m:

Z_m := Z/ = _m.

Z_m has m elements each of which is represented by a natural number less than m, i.e.,

Z_m = {[0]_m, [1]_m, [2]_m, ..., [m-1]_m}.

Before we are going to define the arithmetic operations on this domain, we emphasize an important property of our construction.

Proposition 122 (Congruence Properties) Let a and a' be two integers that are in the same residue class and b and b' be two integers that are also in the same residue class. Then the result of any integer operation involving a and b is in the same residue class as if the operation were performed with a' and b' instead:

forall m in Z_>0, a in Z, a' in Z, b in Z, b' in Z:

   [a]_m = [a']_m /\ [b]_m = [b']_m =>

      [a+b]_m = [a'+b']_m /\

      [a-b]_m = [a'-b']_m /\

      [-a]_m = [-a']_m /\

      [a*b]_m = [a'*b']_m.

Proof Take arbitrary m in Z_>0, a in Z, a' in Z, b in Z, b' in Z such that [a]_m = [a']_m and [b]_m = [b']_m. We show

[a+b]_m = [a'+b']_m.

We know that there exist quotients x, y, z, w and remainders r, s such that

a = xm+r, a' = ym+r,

b = zm+s, b' = wm+s,

which implies

[a+b]_m =

[(xm+r)+(ym+s)]_m =

[(x+y)m+(r+s)]_m = (*)

[(r+s)]_m =

[(z+w)m+(r+s)]_m = (*)

[(zm+r)+(wm+s)]_m =

[a'+b']_m.

(*) It remains to be shown that

forall m in N_>0, x in Z, y in Z: [xm+y]_m = [y]_m.

Example We have [7]₅ = [2]₅ and [9]₅ = [4]₅. Consequently,

[7+9]₅ = [2+4]₅ = [6]₅ = [1]₅.

The importance of the congruence properties is that we may choose any representative of a value of Z_m in order to compute with that value, e.g., when dealing with

[3]₅ = {..., -7, -2, 3, 8, 13, ...}

we need not take the "canonical" representative 3 but may also choose -2 or 8 as the representative for computation. Consequently, the following definition determines the function results uniquely.

Definition 108 (Modular Arithmetic, Residue Classes) Let m in Z_>0 and define the selector function

x := such a in Z: x = [a]_m.

We then define the operations of modular arithmetic (modulare Arithmetik):

+_m: Z_m x Z_m -> Z_m

x +_m y := [x+_Zy]_m

(or: [a]_m +_m [b]_m : = [a+_Zb]_m)

-_m: Z_m x Z_m -> Z_m

x -_m y := [x-_Zy]_m

(or: [a]_m -_m [b]_m : = [a-_Zb]_m)

-_m: Z_m -> Z_m

-_m x := [-_Z x]_m

(or: -_m [a]_m : = [-_Z a]_m)

*_m: Z_m x Z_m -> Z_m

x *_m y := [x*_Z y]_m

(or: [a]_m *_m [b]_m : = [a*_Z b]_m)

For performing arithmetic on some x in Z_m,

we apply the selector function to determine a representative x in Z,
perform the corresponding operation in Z to yield the result r in Z,
and then determine the residue class [r]_m in Z_m.

Example We consider arithmetic in Z₅ = {[0]₅, [1]₅, [2]₅, [3]₅, [4]₅}.

[17]₅+₅[24]₅ = [2]₅ +₅ [4]₅ = [6]₅ = [1]₅

[7]₅-₅[10]₅ = [2]₅ -₅ [0]₅ = [3]₅

[-7]₅ = [3]₅

[6]₅*₅[9]₅ = [1]₅*₅[4]₅ = [4]₅

[-3]₅*₅[6]₅ = [2]₅*₅[1]₅ = [2]₅

Logic Evaluator We can implement modular arithmetic by equivalence classes as shown below, see Appendix modular.txt: the result of a modular operation is an equivalence class of integers <x, y> whose difference x-y denotes the corresponding value.

Author: Wolfgang Schreiner
Last Modification: October 4, 1999

+₃	-4	-3	-2	-1	0	1	2	3	4
-4	1	2	0	1	2	0	1	2	0
-3	2	0	1	2	0	1	2	0	1
-2	0	1	2	0	1	2	0	1	2
-1	1	2	0	1	2	0	1	2	0
0	2	0	1	2	0	1	2	0	1
1	0	1	2	0	1	2	0	1	2
2	1	2	0	1	2	0	1	2	0
3	2	0	1	2	0	1	2	0	1
4	0	1	2	0	1	2	0	1	2

*₃	-4	-3	-2	-1	0	1	2	3	4
-4	1	0	2	1	0	2	1	0	2
-3	0	0	0	0	0	0	0	0	0
-2	2	0	1	2	0	1	2	0	1
-1	1	0	2	1	0	2	1	0	2
0	0	0	0	0	0	0	0	0	0
1	2	0	1	2	0	1	2	0	1
2	1	0	2	1	0	2	1	0	2
3	0	0	0	0	0	0	0	0	0
4	2	0	1	2	0	1	2	0	1

[`a`+`b`]_m	=
[(`xm`+`r`)+(`ym`+`s`)]_m	=
[(`x`+`y`)`m`+(`r`+`s`)]_m	=	(*)
[(`r`+`s`)]_m	=
[(`z`+`w`)`m`+(`r`+`s`)]_m	=	(*)
[(`zm`+`r`)+(`wm`+`s`)]_m	=
[`a`'+`b`']_m.

[17]₅+₅[24]₅	=	[2]₅ +₅ [4]₅ = [6]₅ = [1]₅
[7]₅-₅[10]₅	=	[2]₅ -₅ [0]₅ = [3]₅
[-7]₅	=	[3]₅
[6]₅*₅[9]₅	=	[1]₅*₅[4]₅ = [4]₅
[-3]₅*₅[6]₅	=	[2]₅*₅[1]₅ = [2]₅