31.3 Modular arithmetic
31.3-1¶
Draw the group operation tables for the groups $(\mathbb Z_4, +_4)$ and $(\mathbb Z_5^*, \cdot_5)$. Show that these groups are isomorphic by exhibiting a one-to-one correspondence $\alpha$ between their elements such that $a + b \equiv c \pmod 4$ if and only if $\alpha(a) \cdot \alpha(b) \equiv \alpha(c) \pmod 5$.
$\mathbb Z_4$
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 2 | 3 | 0 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 0 | 1 | 2 |
$\mathbb Z_5^*$
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 |
| 2 | 2 | 4 | 1 | 3 |
| 3 | 3 | 1 | 4 | 2 |
| 4 | 4 | 3 | 2 | 1 |
Define isomorphism $\alpha : \mathbb Z_4 \to \mathbb Z_5^*$ by $\alpha(x) = 2^{x}$.
$a + b \equiv c \pmod 4 \iff 2^{a} \cdot 2^{b} \equiv 2^{c} \pmod 5$
31.3-2¶
List all subgroups of $\mathbb Z_9$ and of $\mathbb Z_{13}^*$.
By Lagrange's Theorem, any subgroup of $\mathbb Z_9$ must be of order $1, 3, 9$. These are
- $\{ 1 \} \cong \mathbb Z_1$
- $\{3, 6, 9\} \cong \mathbb Z_3$
- $\mathbb Z_9$ (not isomorphic to $\mathbb Z_3^2$)
Observe $\mathbb Z_{13}^*$ consists of units $\{1, \dots, 12\}$ and is generated by $2$, i.e. $\mathbb Z_{13}^* = \langle 2 \rangle$. The generators are thus $\langle 2^n \rangle$ for $n | 12$
- $\langle 2 \rangle$
- $\langle 2^2 \rangle = \langle 4 \rangle$
- $\langle 2^3 \rangle = \langle 8 \rangle$
- $\langle 2^4 \rangle = \langle 3 \rangle$
- $\langle 2^6 \rangle = \langle -1 \rangle$
- $\langle 2^{12} \rangle = \langle 1 \rangle$
31.3-3¶
Prove Theorem 31.14.
A nonempty closed subset of a finite group is a subgroup.
- Closure: the subset is closed.
- Identity: suppose $a \in S'$, then $a^{(k)} \in S'$. Since the subset is finite, there must be a period such that $a^{(m)} = a^{(n)}$, hence $a^{(m)}a^{(-n)} = a^{(m - n)} = 1$, therefore the subset must contain the identity.
- Associativity: inherit from the origin group.
- Inverses: suppose $a^{(k)} = 1$, the inverse of element $a$ is $a^{(k - 1)}$ since $aa^{(k - 1)} = a^{(k)} = 1$.
31.3-4¶
Show that if $p$ is prime and $e$ is a positive integer, then
$\phi(p^e) = p^{e - 1}(p - 1)$.
$\phi(p^e) = p^e \cdot \left ( 1 - \frac{1}{p} \right ) = p^{e - 1}(p - 1)$.
31.3-5¶
Show that for any integer $n > 1$ and for any $a \in \mathbb Z_n^*$, the function $f_a : \mathbb Z_n^* \rightarrow \mathbb Z_n^*$ defined by $f_a(x) = ax \mod n$ is a permutation of $\mathbb Z_n^*$.
To prove it is a permutation, we need to prove that
- for each element $x \in \mathbb Z_n^*$, $f_a(x) \in \mathbb Z_n^*$,
- the numbers generated by $f_a$ are distinct.
Since $a \in \mathbb Z_{n}^*$ and $x \in \mathbb Z_n^*$, then $f_a(x) = ax \mod n \in \mathbb Z_n^*$ by the closure property.
Suppose there are two distinct numbers $x \in \mathbb Z_n^*$ and $y \in \mathbb Z_n^*$ that $f_a(x) = f_a(y)$,
$$ \begin{aligned} f_a(x) & = f_a(y) \\ ax \mod n & = ay \mod n \\ (a \mod n)(x \mod n) & = (a \mod n)(y \mod n) \\ (x \mod n) & = y \mod n \\ x & \equiv y \mod n, \end{aligned} $$
which contradicts the assumption, therefore the numbers generated by $f_a$ are distinct.