Modular Arithmetic

Most of us learn early in our schooling the concept of a remainder, that when dividing whole numbers the denominator will only divide the numerator a certain number of times and a remainder is left. (For instance 45/7 = 6 remainder 3.

The remainder left, takes an y value from 0 to n-1 for division by n. Those numbers left over form "equivalence classes" in the sense that '~' means "share the same class"

1) if a is in some class, then a~a

2)if a~b, then b~a

3) if a~b and b~c then a~c.

Alternatively, the well known operations of addition and multiplication are well defined upon these classes. We may write the member of any class as;

a≅b mod n, where a~b.

Or indeed, "n divides a-b"

Therefore...

a≅b mod n, c≅d mod n implies
a - b = rn,
c - d = sn.

|So, a+c≅b+d mod n
[a+c = (b + d) + (r +s)n]

and, ac ≅ bd mod n
[ac = (b + rn)(d + sn) = bd + drn + bsn + rsnn = bd + (dr + bs + rsn)n]

Since no integers except p and 1 divide a prime number p, there are no zero divisors of set of classes 'mod p'. (properly said 'modulo p'). This also means that any repeated sum of elements n+n+n+...+n requires p summands to reach zero. pn=0. 'p' is called the 'characteristic' of the set of classes mod p. Since the distributive laws are inherited from the ring of integers, These classes form a Ring, Zp, (or Z/pZ). The characteristic of a ring is defined as the least integer m such that for every element x of the ring, x+x+...+x with m summands is zero. Equivalently using unity instead of x in a ring with unity yields the same result.

So, since there are p elements in Zp, and the characteristic of Zp is p, The additive group is 'cyclic', since for all elements in Zp are equal to some n summands of any other particular non-zero element. It is also true that Zp is a finite field. It can also be shown that every finite field has a cyclic multiplicative group.

Continue To Next Page

Return To Section Start

Return To Previous Page