Skip to content

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.