跳转至

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.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用