Go backward to 7.1.1 Basic NotionsGo up to 7.1 Equivalence Relations and PartitionsGo forward to 7.1.3 Another Construction of Number Domains |

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^{40}*2^{30}. 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.

+ _{m}:ZxZ->Z_{m}x+_{m}y:= (x+y) modm- _{m}:ZxZ->Z_{m}x-_{m}y:= (x-y) modm- _{m}:ZxZ->Z_{m}- _{m}x:= (-x) modm* _{m}:ZxZ->Z_{m}x*_{m}y:= (x*y) modm

+ _{3}-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

* _{3}-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`+3`i` for any `i` in **Z**. We may therefore define
the set of all values

[that cannot be distinguished froma]_{m}:= {a+im:iinZ}

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

x=_{m}y: <=> (xmodm) = (ymodm).

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`.

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

It is easy to see that [`a`]_{m} =
{`a`+`i``m`: `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.

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.

forallminZ_{>0},ainZ,a' inZ,binZ,b' inZ:[ 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}.

We know that there exist quotients

[ a+b]_{m}= [a'+b']_{m}.

which implies

a=xm+r,a' =ym+r,b=zm+s,b' =wm+s,

(*) It remains to be shown that

[ 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}.

forallminN_{>0},xinZ,yinZ: [xm+y]_{m}= [y]_{m}.

[7+9]_{5}= [2+4]_{5}= [6]_{5}= [1]_{5}.

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]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._{5}= {..., -7, -2, 3, 8, 13, ...}

We then define the operations of

:=xsuchainZ:x= [a]_{m}.

+ _{m}:Z_{m}xZ_{m}->Z_{m}x+_{m}y:= [+x_{Z}]y_{m}(or: [ a]_{m}+_{m}[b]_{m}: = [a+_{Z}b]_{m})- _{m}:Z_{m}xZ_{m}->Z_{m}x-_{m}y:= [-x_{Z}]y_{m}(or: [ a]_{m}-_{m}[b]_{m}: = [a-_{Z}b]_{m})- _{m}:Z_{m}->Z_{m}- _{m}x:= [-_{Z}]x_{m}(or: - _{m}[a]_{m}: = [-_{Z}a]_{m})* _{m}:Z_{m}xZ_{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
in`x`**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}.

[17] _{5}+_{5}[24]_{5}= [2] _{5}+_{5}[4]_{5}= [6]_{5}= [1]_{5}[7] _{5}-_{5}[10]_{5}= [2] _{5}-_{5}[0]_{5}= [3]_{5}[-7] _{5}= [3] _{5}[6] _{5}*_{5}[9]_{5}= [1] _{5}*_{5}[4]_{5}= [4]_{5}[-3] _{5}*_{5}[6]_{5}= [2] _{5}*_{5}[1]_{5}= [2]_{5}

`modular.txt`

Author: Wolfgang Schreiner

Last Modification: October 4, 1999