Recall that $\mathbb{Z}_{n}$ is the set of congruence classes modulo $n$.
2. Remark 1: Convention on notation
Given a fixed integer $n$ we will often identity an integer number $a \in \mathbb{Z}$ with the corresponding congruence class in $\mathbb{Z}_{n}$. For example we will write
$$
5 \in \mathbb{Z}_{7}
$$
assuming the congruence class of integers [5] modulo 7. In particular we can write
$$
5=19 \text { in } \mathbb{Z}_{7}
$$
since 5 and 19 belong to the same congruence class.
This allows us, by abuse of notation, write
$$
\mathbb{Z}_{n}={0,1,2 \ldots, n-1}
$$
instead of the formally correct
$$
\mathbb{Z}_{n}={[0],[1],[2], \ldots,[n-1]}
$$
An element $k \in \mathbb{Z}{n}$ is called a $u n i t$, if there exists an element $l \in \mathbb{Z}{n}$ such that
$$
k \cdot l=1 \text { in } \mathbb{Z}_{n}
$$
The following theorem provide a complete characterization of units in $\mathbb{Z}_{n}$.
3. Theorem 1: Characterization of units in $\mathbb{Z}_{n}$
Let $n \geqslant 2$ be an integer. The set of units in $\mathbb{Z}{n}\left(\right.$ denoted $\left.\mathbb{Z}{n}^{\times}\right)$consists of all congruence class of integers coprime to $n$ :
$$
\mathbb{Z}{n}^{\times}=\left{k \in \mathbb{Z}{n} \mid \operatorname{gcd}(n, k)=1\right}
$$
Proof. Let $k \in{0, \ldots, n-1}$.
- If $\operatorname{gcd}(n, k)=1$, then by the theorem from the previous week, we can find integers $u, v \in \mathbb{Z}$ such that
$$
n u+k v=1 .
$$
Therefore, in $\mathbb{Z}_{n}$ we have
$$
k \cdot v \equiv 1 \quad \bmod n
$$
so that $[v]$ is the multiplicative inverse of $[k]$ in $\mathbb{Z}_{n} .$
- Conversely, if we can find a multiplicative inverse to $[k] \in \mathbb{Z}_{n}$ :
$$
k \cdot l \equiv 1 \quad \bmod n
$$
then any common divisor of $k$ and $n$ would also divide 1, so necessarily $\operatorname{gcd}(n, k)=1 .$
In $\mathbb{Z}_{6}$ the only units are 1 and $5=-1$.
Given integer $n \geqslant 2$, define Euler’s function $\varphi(n)$ to be the number of integers in ${1, \ldots, n-1}$ which a coprime with $n$. In other words,
$$
\left|\mathbb{Z}_{n}^{\times}\right|=\varphi(n)
$$
Problem 1: Number $n$ is prime, if and only if $\varphi(n)=n-1 .$
Let $S$ be an arbitrary set.
8. Definition 2: Law of composition
A law of composition (or binary operation) on $S$ is a function
$$
S \times S \rightarrow S
$$
which assigns to any pair $(x, y) \in S \times S$ an element $x * y \in S$. (Instead of $x * y$ often we will write $x \cdot y$, or even $x y$ )
Addition and multiplication are composition laws on $\mathbb{Z}$.
Division is not a composition law on $\mathbb{R}$, since $x / 0$ is not defined. However, it is a composition law on $\mathbb{R} \backslash{0} .$
10. Example 3: Important example
Let $X$ be an arbitrary set, and consider
$$
S=\mathcal{F}(X, X)
$$
to be the set of all maps $f: X \rightarrow X$. Given a pair of maps $f, g \in \mathcal{F}(X, X)$, we can take their composition and obtain an element $f \circ g \in \mathcal{F}(X, X)$. Hence, the composition of maps defines a law of composition on $\mathcal{F}(X, X)$ (thus the name).
Let
$$
\begin{gathered}
S \times S \rightarrow S \
(x, y) \mapsto x * y
\end{gathered}
$$
be a law of composition on $S$. We say that * is
- associative, if for any $x, y, z \in S$ we have
$$
(x * y) * z=x *(y * z) .
$$
- commutative, if for any $x, y \in S$
$$
x * y=y * x
$$
If the law of composition is associative, given $x_{1}, \ldots, x_{n} \in S$, it makes sense to write just
$$
x_{1} * x_{2} * \cdots * x_{k}
$$
without any brackets.
Traditionally, we drop the symbol * and denote a law of composition by $(x, y) \mapsto x y($ this is called the multiplicative notation), but if it happens to be commutative, the additive notation $(x, y) \mapsto x+y$ may be used. For the moment, for clarity, we will keep using the symbol *.
Let $(S, *)$ be a set with a composition law. We say that $e \in S$ is an identity (or neutral element) if for all $x \in S$ we have
$$
x * e=e * x=x .
$$
Problem 2: Any law of composition has at most one identity element.
Hint: given two identities $e, e^{\prime}$ consider $e * e^{\prime}$.
Let $(S, *)$ be a set with a composition law with an identity e. We say that $y \in S$ is invertible if there exists $x \in S$ such that
$$
x * y=y * x=e \text {. }
$$
The inverse of $y$ is denoted by $y^{-1}$.
Clearly, $e$ is invertible with $e^{-1}=e$.
Let $(S, *)$ be a set with an associative composition law and identity. Let $x, y \in S$ be two invertible elements, then $x * y$ is also invertible with $(x * y)^{-1}=y^{-1} * x^{-1}$
Proof. Indeed, we have
$$
(x * y) *\left(y^{-1} * x^{-1}\right)=x *\left(y * y^{-1}\right) * x^{-1}=x * e * x^{-1}=x * x^{-1}=e
$$
where in the first equality we used associativity, in the second the fact that $y^{-1}$ is the inverse of $y$, in the third the property of the identity $e$, and in the last the fact that $x^{-1}$ is the inverse of $x .$
Similarly we check that $\left(y^{-1} * x^{-1}\right) *(x * y)=e$ which proves that $\left(y^{-1} * x^{-1}\right)=(x * y)^{-1}$.
15. Example 4: Key motivating example
Let $\Delta$ be an equilateral triangle. Then it has 6 symmetries:
- 3 rotations – by $0^{\circ}, 120^{\circ}$ and $240^{\circ}$ (denote them $\tau_{0}, \tau_{1}, \tau_{2}$ )
- 3 reflections along 3 altitudes (denote them by $\sigma_{1}, \sigma_{2}, \sigma_{3}$ ).
We claim that the composition operation on the set $\left{\tau_{0}, \tau_{1}, \tau_{2}, \sigma_{1}, \sigma_{2}, \sigma_{3}\right}$ defines a law of composition (exercise).
Problem 3: Prove that the above law of composition is associative, has an identity and every element admits an inverse.
Let $(G, *)$ be a set with a law of composition. We will say that $(G, *)$ si a group if the following properties hold:
- * is associative
- there is an identity $e \in G$
- every element $x \in G$ is invertible.