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, +_4)$: $\{ 0, 1, 2, 3 \}$.
- $(\mathbb Z_5^*, \cdot_5)$: $\{ 1, 2, 3, 4 \}$.
$\alpha(x) = 2^{x-1}$.
31.3-2¶
List all subgroups of $\mathbb Z_9$ and of $\mathbb Z_{13}^*$.
-
$\mathbb Z_9$:
- $\langle 0 \rangle = \{ 0 \}$,
- $\langle 1 \rangle = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8 \}$,
- $\langle 2 \rangle = \{ 0, 2, 4, 6, 8 \}$.
-
$\mathbb Z_{13}^*$:
- $\langle 1 \rangle = \{ 1 \}$,
- $\langle 2 \rangle = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 \}$.
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.