Modular arithmetic and the ring of integers modulo \(n\)

Section 2.3 Modular arithmetic and the ring of integers modulo \(n\)

We will now examine the main space of numbers used in early modern mathematical cryptographic methods like RSA and Elgamal.

Definition 2.3.1.

Two integers \(a\) and \(b\) are congruent modulo \(n\) if their difference \(a - b\) is divisible by \(n\text{.}\) In symbols, we write

\begin{equation*} a \equiv b\bmod n \text{ if and only if } n\mid (a - b) \end{equation*}

The division algorithm and the above definition give another characterization of this congruence: \(a \equiv b \bmod n\) if and only if the remainders of \(a\) and \(b\) after division by \(n\) are equal.

Question 2.3.2.

Show that the two characterizations are logically equivalent.

Congruence mod \(n\) is an example of a special kind of relation called an equivalence relation, which is a major object of study in number theory and modern algebra. Here, we'll satisfy ourselves with the statement that equivalence relations behave much like equality; in particular, modular arithmetic almost gives a completely consistent structure for doing the usual algebra of the integers, as the next theorem states:

Theorem 2.3.3.

\(m \geq 1\)

If \(a_1 \equiv a_2 \bmod n\) and \(b_1 \equiv b_2 \bmod n\) then

\begin{equation*} a_1 \pm b_1 \equiv a_2 \pm b_2 \bmod n \text{ and } a_1 \cdot b_1 \equiv a_2 \cdot b_2 \bmod n. \end{equation*}
Let \(a\) be an integer. Then

\begin{equation*} a \cdot b \equiv 1 \bmod n \text{ for some integer if and only if } \gcd(a,n) = 1. \end{equation*}

If \(b\) exists, it is unique, and it is called the inverse of \(a\text{.}\)

Part (2) of Theorem 3.3 essentially characterizes which integers \(a\) have multiplicative inverses modulo \(n\text{.}\) Since the inverse is unique, we give it a special symbol, \(a\inv\text{.}\) Note that this is NOT the inverse in the rational numbers given by the reciprocal of \(a\text{.}\) For example, since \(2 \cdot 3 \equiv 1 \bmod 5\text{,}\) we can say \(2\inv = 3\) and \(3\inv = 2\text{.}\) This leads to amusing notational oddities of statements like \(\frac{4}{3} \equiv 4 \cdot 3\inv \equiv 4 \cdot 2 \equiv 3 \bmod 5\text{.}\)

The extended Euclidean algorithm, Theorem 2.2.5, explicitly computes inverses modulo \(n\) when they exist. To see this, assume that \(\gcd(a,n) = 1\) so that \(a\) possesses an inverse \(\bmod n\text{.}\) Applying Theorem Theorem 2.2.5 produces integers \(u, v\) so that

\begin{equation*} a u + n v = 1. \end{equation*}

Then

\begin{equation*} a u - 1 = n v \end{equation*}

which implies that \(n \mid (au - 1)\text{.}\) Then by the definition of congruence mod \(n\text{,}\) we get \(au \equiv 1 \pmod n\text{,}\) and thus we can take \(a\inv = u\text{.}\)

Thinking about congruence mod \(n\) as measuring the remainder when an integer is divided by \(n\text{,}\) it should be clear that every integer must be congruent mod \(n\) to one of the positive integers \(0, \ldots, n-1\) (as these are all of the possible remainders after dividing by \(n\)). Furthermore, Theorem 2.3.3 tells us that addition, subtraction, and multiplication are well-defined operations on the set \(\{0, \ldots, n-1\}\text{,}\) in the sense that these operations allow arithmetic and a good deal of algebra to be performed on the set. With this in mind, we define the ring of integers modulo \(n\), denoted by the symbol \(\Z_n\) by

\begin{equation*} \Z_n = \{0, 1, \ldots, n-1\} \text{ with addition and multiplication} \pmod n. \end{equation*}

Note 2.3.4.

The term ring refers to a set equipped with two operations, + and \(\cdot\text{,}\) that satisfy a certain number of algebraic properties characteristic of addition and multiplication in \(\Z\text{.}\) (Perhaps the most distinguishing characteristic is that there is a distributive property that intertwines the operations.) Rings are a central object in the study of modern algebra, along with groups, which are sets equipped with a single operation. In fact, we are just about to meet an extremely important group that lives inside \(\Z_n\ldots\)

Definition 2.3.5.

An integer \(a\) is a unit in \(\Z_n\) if \(a\) has an inverse \(a\inv\) modulo \(n\text{.}\)

The units of \(\Z_n\) are important because they are the objects in \(\Z_n\) that can be “divided”, in the sense of algebraic cancellation. Living inside \(\Z_n\) is the smaller set consisting of the units in \(\Z_n\text{.}\) Because the product of two units is a unit (you should convince yourself that this is the case), the set of units are closed under multiplication and thus form a group with identity element 1.

Definition 2.3.6.

The group of units in \(\Z_n\) is the set of units in \(\Z_n\) with operation multiplication \(\pmod n\text{.}\) It is denoted \(\Z_n\ad\text{.}\)

We are going to be interested in counting how many units a particular \(\Z_n\) contains. This will be possible after observing that

\(a\) is a unit if it has an inverse mod \(n\)
\(a\) has an inverse mod \(n\) if it is relatively prime with \(n\) (Theorem 2.3.3)

Thus, to count the units in \(Z_n\text{,}\) we need to count the integers \(a\) with \(0 \leq a \lt n\) and \(\gcd(a,n) = 1\text{.}\) The classical function used to denote this count is called the Euler phi function or the totient function, and is denoted

\begin{equation*} \phi(n) = \text{ number of elements in } \{a \in \Z, 0\leq a \lt n: \gcd(a, n) = 1\}. \end{equation*}

Mathematical Cryptography