Modular artithmetic

 

Modular arithmetic[edit]

Main article: Modular arithmetic

The hours on a clock form a group that uses addition modulo 12. Here, 9 + 4 ≡ 1.

Modular arithmetic for a modulus $�$ defines any two elements $�$ and $�$ that differ by a multiple of $�$ to be equivalent, denoted by ${\displaystyle �\equiv �(\mathrm{mod}�)}$. Every integer is equivalent to one of the integers from ${\displaystyle 0}$ to $�-1$, and the operations of modular arithmetic modify normal arithmetic by replacing the result of any operation by its equivalent representative. Modular addition, defined in this way for the integers from ${\displaystyle 0}$ to $�-1$, forms a group, denoted as ${\displaystyle {\mathrm{Z}}_{�}}$ or ${\displaystyle (\mathbb{�}/�\mathbb{�},+)}$, with ${\displaystyle 0}$ as the identity element and ${\displaystyle �-�}$ as the inverse element of $�$.

A familiar example is addition of hours on the face of a clock, where 12 rather than 0 is chosen as the representative of the identity. If the hour hand is on $9$ and is advanced $4$ hours, it ends up on $1$, as shown in the illustration. This is expressed by saying that ${\displaystyle 9+4}$ is congruent to $1$ "modulo $12$" or, in symbols,

$${\displaystyle 9+4\equiv 1(\mathrm{mod}12).}$$

For any prime number $�$, there is also the multiplicative group of integers modulo $�$.^[43] Its elements can be represented by $1$ to $�-1$. The group operation, multiplication modulo $�$, replaces the usual product by its representative, the remainder of division by $�$. For example, for $�=5$, the four group elements can be represented by $1,2,3,4$. In this group, ${\displaystyle 4\cdot 4\equiv 1mod5}$, because the usual product $16$ is equivalent to $1$: when divided by $5$ it yields a remainder of $1$. The primality of $�$ ensures that the usual product of two representatives is not divisible by $�$, and therefore that the modular product is nonzero.^[m] The identity element is represented by $1$, and associativity follows from the corresponding property of the integers. Finally, the inverse element axiom requires that given an integer $�$ not divisible by $�$, there exists an integer $�$ such that

$${\displaystyle �\cdot �\equiv 1(\mathrm{mod}�),}$$

that is, such that $�$ evenly divides ${\displaystyle �\cdot �-1}$. The inverse $�$ can be found by using Bézout's identity and the fact that the greatest common divisor ${\displaystyle gcd(�,�)}$ equals $1$.^[44] In the case $�=5$ above, the inverse of the element represented by $4$ is that represented by $4$, and the inverse of the element represented by $3$ is represented by $2$, as ${\displaystyle 3\cdot 2=6\equiv 1mod5}$. Hence all group axioms are fulfilled. This example is similar to ${\displaystyle \left(\mathbb{�}\setminus \left\{0\right\},\cdot \right)}$ above: it consists of exactly those elements in the ring ${\displaystyle \mathbb{�}/�\mathbb{�}}$ that have a multiplicative inverse.^[45] These groups, denoted ${\displaystyle {\mathbb{�}}_{�}^{\times }}$, are crucial to public-key cryptography.^[n]

Cyclic groups[edit]

Main article: Cyclic group

The 6th complex roots of unity form a cyclic group. $�$ is a primitive element, but ${�}^2$ is not, because the odd powers of $�$ are not a power of ${�}^2$.

A cyclic group is a group all of whose elements are powers of a particular element $�$.^[46] In multiplicative notation, the elements of the group are

$${\displaystyle \dots ,{�}^{-3},{�}^{-2},{�}^{-1},{�}^0,�,{�}^2,{�}^3,\dots ,}$$

where ${�}^2$ means ${\displaystyle �\cdot �}$, ${�}^{-3}$ stands for ${\displaystyle {�}^{-1}\cdot {�}^{-1}\cdot {�}^{-1}=(�\cdot �\cdot �{)}^{-1}}$, etc.^[o] Such an element $�$ is called a generator or a primitive element of the group. In additive notation, the requirement for an element to be primitive is that each element of the group can be written as

$${\displaystyle \dots ,(-�)+(-�),-�,0,�,�+�,\dots .}$$

In the groups ${\displaystyle (\mathbb{�}/�\mathbb{�},+)}$ introduced above, the element $1$ is primitive, so these groups are cyclic. Indeed, each element is expressible as a sum all of whose terms are $1$. Any cyclic group with $�$ elements is isomorphic to this group. A second example for cyclic groups is the group of $�$th complex roots of unity, given by complex numbers $�$ satisfying ${\displaystyle {�}^{�}=1}$. These numbers can be visualized as the vertices on a regular $�$-gon, as shown in blue in the image for $�=6$. The group operation is multiplication of complex numbers. In the picture, multiplying with $�$ corresponds to a counter-clockwise rotation by 60°.^[47] From field theory, the group ${\displaystyle {\mathbb{�}}_{�}^{\times }}$ is cyclic for prime $�$: for example, if $�=5$, $3$ is a generator since ${\displaystyle 3^1=3}$, ${\displaystyle 3^2=9\equiv 4}$, ${\displaystyle 3^3\equiv 2}$, and ${\displaystyle 3^4\equiv 1}$.

Some cyclic groups have an infinite number of elements. In these groups, for every non-zero element $�$, all the powers of $�$ are distinct; despite the name "cyclic group", the powers of the elements do not cycle. An infinite cyclic group is isomorphic to ${\displaystyle (\mathbb{�},+)}$, the group of integers under addition introduced above.^[48] As these two prototypes are both abelian, so are all cyclic groups.

The study of finitely generated abelian groups is quite mature, including the fundamental theorem of finitely generated abelian groups; and reflecting this state of affairs, many group-related notions, such as center and commutator, describe the extent to which a given group is not abelian.^[49]