Multiplicative groups modulo m

We know how to do arithmetic operations -- addition and multiplication -- modulo some fixed positive integer. If this integer is a prime number, modular multiplication shows some non-obvious properties, having very practical applications -- in fact, secure communications today heavily rely on these properties. Let's see what they are.

Modular arithmetic: a brief recap

Firstly, let's recall that when doing arithmetic operations modulo $m$, we replace all integers with their residues (in other words, the remainders obtained when we divide these integers by $m$). The set $\mathbb{Z}_m$ of these residues is, in fact, a range $\{0, 1, \ldots m − 1\}$. But, to avoid confusion between usual operations and modular ones, we write the residues with a line over them:

$$\mathbb{Z}_m = \{\overline{0},\overline{1}, \ldots, \overline{m-1}\}$$Now, if we fix some $m$ (let $m = 7$), we can write simply

$$\overline{3} + \overline{6} = \overline{2}\\ \overline{3} \cdot \overline{6} = \overline{4}\\$$instead of $$3 + 6 \equiv 2 \pmod 7 \\ 3 \cdot 6 \equiv 4 \pmod 7 \\$$Of course, the "overlined" notation works only if we explicitly indicate $m$.

We have already seen that $\mathbb{Z}_m$ is a group with respect to modular addition. The addition operation is associative, $\overline{0}$ is a neutral element, and $\overline{m - x}$ is an additive inverse for $\overline{x}$. Note that the group properties hold for any positive $m$ -- even for $m = 1$, although in this case $\mathbb{Z}_m$ is a trivial group containing only one element $\overline{0}$.

The group of units modulo m

But do the group properties hold when we consider $\mathbb{Z}_m$ with the operation of modular multiplication? Let's check! From now on, we will talk about $m \geq 2$.

We start with a promising observation that modular multiplication is associative. The next property to check is the existence of a neutral element. And here it is: $$\overline{1} \cdot \overline{x} = \overline{x} \cdot \overline{1} = \overline{x} \text{ for any } \overline{x} \in \mathbb{Z}_{m}$$But with the third property -- the existence of inverse for any element -- we encounter a problem. For example, $\overline{0}$ has no inverse, because $\overline{x} \cdot \overline{0} = \overline{0}$ for any $\overline{x} \in \mathbb{Z}_{m}$. In general, the residues that are relatively prime to $m$ -- and only them -- have inverses (which can be found using Euclid's algorithm).

So let's consider not the whole set $\mathbb{Z}_m$, but only its invertible elements, the residues relatively prime to $m$. Such residues are also called units modulo $m$. The set of units will be denoted as $\mathbb{Z}^{*}_m$. Note that a product of two units $\overline{a} \in \mathbb{Z}^{*}_{m}$ and $\overline{b} \in \mathbb{Z}^{*}_{m}$ will also be a unit (check that the product of inverses for $\overline{a}$ and $\overline{b}$ will be an inverse for their product!)

For $m = 8$, there are 4 units modulo $m$ :

$$\mathbb{Z}^{*}_{8} = \{\overline{1}, \overline{3}, \overline{5}, \overline{7} \}$$and there is the same number of units modulo $m = 12$:

$$\mathbb{Z}^{*}_{12} = \{\overline{1}, \overline{5}, \overline{7}, \overline{11} \}$$

In fact, $\mathbb{Z}^{*}_m$ is a group with respect to modular multiplication -- the operation is associative, $\overline{1}$ is a neutral element, and every unit has an inverse. For instance, in $\mathbb{Z}^{*}_{8}$ every element is its own inverse: $$\overline{1} \cdot \overline{1} = \overline{1}, \text { since } 1 \cdot 1 \equiv 1 \pmod{8},\\ \overline{3} \cdot \overline{3} = \overline{1}, \text { since } 3 \cdot 3 \equiv 9 \equiv 1 \pmod{8},\\ \overline{5} \cdot \overline{5} = \overline{1}, \text { since } 5 \cdot 5 \equiv 25 \equiv 1 \pmod{8},\\ \overline{7} \cdot \overline{7} = \overline{1}, \text { since } 7 \cdot 7 \equiv 49 \equiv 1 \pmod{8},\\$$But this is not a property shared by all groups of units -- you can check that in $\mathbb{Z}^{*}_{9}$,

$$\overline{2} \cdot \overline{5} = \overline{1}, \text{ since } 2 \cdot 5 \equiv 10 \equiv 1 \pmod{9}$$

The group of units modulo a prime

How many elements are there in the group of units $\mathbb{Z}^{*}_m$? Of course, the answer depends on $m$. There is a special name and notation for this dependency.

Definition. Euler's phi function (also sometimes known as Euler's totient function) is defined as

$$\phi(m) = \vert \mathbb{Z}^{*}_{m}\vert$$That is, $\phi(m)$ is the number of units modulo $m$ (or, equivalently, the number of integers in the range $\{0, 1, \ldots m − 1\}$ relatively prime to $m$).

There exists a simple general formula for $\phi(m)$ , but for now, we'll only say that

$$\phi(p) = p - 1 \text{ for any prime } p$$Indeed, every integer in the range $\{0, 1, \ldots p − 1\}$, except zero, is relatively prime to $p$:

$$\mathbb{Z}^{*}_{p} = \{\overline{1},\ldots, \overline{p - 1}\}$$But in fact, $\mathbb{Z}^{*}_{p}$ possesses another more interesting property. It is not only a group but a cyclic group.

Definition. A group $(G, \cdot)$ is called cyclic if there exists an element $g \in G$ such that every element $h \in G$ is a power of $g$:

$$h = g^{x} \text{ for some integer } x$$The element $g$ is called a generator of the cyclic group.

It turns out that for any $p$, the group $\mathbb{Z}^{*}_{p}$ possesses a generator. Let's look at $\mathbb{Z}^{*}_{11}$, for example. The residue $\overline{2}$ will be a generator, since

$$\overline{2}^{0} = \overline{1}, \quad \overline{2}^{1} = \overline{2}, \\ \overline{2}^{2} = \overline{4}, \quad \overline{2}^{3} = \overline{8}, \\ \overline{2}^{4} = \overline{5}, \quad \overline{2}^{5} = \overline{10}, \\ \overline{2}^{6} = \overline{9}, \quad \overline{2}^{7} = \overline{7},\\ \overline{2}^{8} = \overline{3}, \quad \overline{2}^{9} = \overline{6}$$Computing the powers of $\overline{2}$, we obtain each of the 10 elements of $\mathbb{Z}^{*}_{11}$.

Generators in $\mathbb{Z}^{*}_{p}$ also have a special name -- they are called primitive roots modulo $p$. $\overline{2}$ and $\overline{6}$ are primitive roots modulo 11. If you know some programming language or just have enough patience, you can try to find all primitive roots modulo 11 (or modulo some larger prime).

Conclusion

In this topic, we went through the basics of Modular arithmetics, here are some of the main points:

• Modular arithmetic operations on the set $\mathbb{Z}_m$ are addition and multiplication but of residues modulo $m$.
• We showed that the set $\mathbb{Z}^{*}_m$ of invertible residues (units modulo $m$), is a group with respect to modular multiplication that consists of only those elements of $\mathbb{Z}_m$ that are prime relative to $m$.
• We noted that $(\mathbb{Z}^{*}_p, \cdot)$ is a cyclic group containing $p-1$ elements. Such that $h = g^{x}$ where $g$ is called a generator of the cyclic group and we can obtain all elements of the group by only changing the power $x$.