5.1: Modular Arithmetic

Last updated
Save as PDF

Page ID: 60321

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Modular Arithmetic concerns itself with computations involving addition and multiplication in \(\mathbb{Z}\) module \(b\), denoted by \(\mathbb{Z}_{b}\), 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 \sim 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 \(\ast\) on a set \(G\) and that \((G, \ast)\) 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 \ast g \cdots g\), repeated \(k\) times and usually written \(g^k\), equals \(e\). One can show that the elements \(\{e, g, g^2, g^{k-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, \(\mathbb{Z}^b\), 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 \(\mathbb{Z}^b\) with respect to addition and with respect to multiplication. As an example, we consider the element \(3\) in \(\mathbb{Z}^7\):

\[\begin{array}{ccc} {3+3+3+3+3+3+3 = _{7} 0}&{\mbox{and}}&{3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 = _{7} 1} \nonumber \end{array}\]

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 \(\mbox{Ord}^{\times}_{b} (a)\), is the smallest positive number \(k\) such that \(a^{k} = _{b} 1\). (If there is no such \(k\), the order is \(\infty\).)