5.1: Modular Arithmetic
( \newcommand{\kernel}{\mathrm{null}\,}\)
Modular Arithmetic concerns itself with computations involving addition and multiplication in Z module b, denoted by Zb, i.e, calculations with residues module b (See definition 1.6). One common way of looking at this is to consider integers x and y that differ by a multiple of b as equivalent (see exercise 5.1). We write x∼y. One then proves that the usual addition and multiplication is well-defined for these equivalence classes. This is done in exercise 5.2.
Suppose we are given an operation ∗ on a set G and that (G,∗) satisfies certain requirements - namely that it forms as group - that include having an identity element e. The order of an element g is the smallest positive integer k such that g∗g⋯g, repeated k times and usually written gk, equals e. One can show that the elements {e,g,g2,gk−1} also form a group. To follow this up would take us too far a field. A few details are given in Chapter ??. The full story can be found in [10], [11], or [13].
In the case at hand, Zb, where we have a structure with two operations, namely addition with identity element 0 and multiplication with identity element 1. We could therefore define the order of an element in Zb with respect to addition and with respect to multiplication. As an example, we consider the element 3 in Z7:
3+3+3+3+3+3+3=70and3⋅3⋅3⋅3⋅3⋅3=71
The first gives 7 as the additive order of 3, and the second gives 6 for the multiplicative order. For our current purposes, however, it is sufficient to work only with the multiplicative version.
Definition 5.1
The order of a modulo b, written as Ord×b(a), is the smallest positive number k such that ak=b1. (If there is no such k, the order is ∞.)