Isomorphism between Additive Group Modulo 16 and Multiplicative Group Modulo 17

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {\Z_{16}, +}$ denote the additive group of integers modulo $16$.

Let $\struct {\Z'_{17}, \times}$ denote the multiplicative group of reduced residues modulo $17$.

Let $\phi: \struct {\Z_{16}, +} \to \struct {\Z'_{17}, \times}$ be the mapping defined as:

$\forall \eqclass k {16} \in \struct {\Z_{16}, +}: \map \phi {\eqclass k {16} } = \eqclass {3^k} {17}$


Then $\phi$ is a group isomorphism.


Proof

Let $\eqclass x {16}, \eqclass y {16} \in \struct {\Z_{16}, +}$.

Then:

\(\displaystyle \map \phi {\eqclass x {16} } \times \map \phi {\eqclass y {16} }\) \(=\) \(\displaystyle \map \phi {x + 16 m_1} \times \map \phi {y + 16 m_2}\) Definition of Residue Class: for some representative $m_1, m_2 \in \Z$
\(\displaystyle \) \(=\) \(\displaystyle 3 \uparrow \paren {x + 16 m_1} \times 3 \uparrow \paren {y + 16 m_2}\) using Knuth uparrow notation $3 \uparrow k := 3^k$
\(\displaystyle \) \(=\) \(\displaystyle 3 \uparrow \paren {x + 16 m_1 + y + 16 m_2}\) Product of Powers
\(\displaystyle \) \(=\) \(\displaystyle 3 \uparrow \paren {\paren {x + y} + 16 \paren {m_1 + m_2} }\)
\(\displaystyle \) \(=\) \(\displaystyle 3 \uparrow \paren {\eqclass {x + y} {16} }\) Definition of Residue Class and Definition of Modulo Addition
\(\displaystyle \) \(=\) \(\displaystyle \map \phi {\eqclass x {16} + \eqclass y {16} }\) Definition of $\phi$

Thus it is seen that $\phi$ is a group homomorphism.

$\Box$


It remains to be seen that $\phi$ is a bijection.


Because $17$ is prime: $\forall x \in \Z, 1 \le x < 17: x \perp 17$ where $\perp$ denotes coprimality.

Thus by definition of multiplicative group of reduced residues modulo $17$:

$\order {\struct {\Z'_{17}, \times} } = 16$

where $\order {\, \cdot \,}$ denotes the order of a group.

Similarly, by definition of additive group of integers modulo $16$:

$\order {\struct {\Z_{16}, +} } = 16$

So:

$\order {\struct {\Z'_{17}, \times} } = \order {\struct {\Z_{16}, +} }$

which is a necessary condition for group isomorphism.

$\Box$


Now we have:

\(\displaystyle 16\) \(\equiv\) \(\displaystyle 0\) \(\displaystyle \pmod {16}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map \phi {\eqclass {16} {16} }\) \(=\) \(\displaystyle \map \phi {\eqclass 0 {16} }\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map \phi {\eqclass {16} {16} }\) \(=\) \(\displaystyle \eqclass 1 {17}\) Group Homomorphism Preserves Identity
\((1):\quad\) \(\displaystyle \leadsto \ \ \) \(\displaystyle 3^{16}\) \(\equiv\) \(\displaystyle 1\) \(\displaystyle \pmod {17}\) Definition of $\phi$


Now let $\eqclass x {16}, \eqclass y {16} \in \Z_{16}$ such that $\map \phi {\eqclass x {16} } = \map \phi {\eqclass y {16} }$.

We have:

\(\displaystyle \map \phi {\eqclass x {16} }\) \(=\) \(\displaystyle \map \phi {\eqclass y {16} }\)
\(\displaystyle \leadsto \ \ \) \(\, \displaystyle \forall m_1, m_2 \in \Z \, \) \(\displaystyle \map \phi {x + 16 m_1}\) \(=\) \(\displaystyle \map \phi {y + 16 m_2}\) Definition of Residue Class
\(\displaystyle \leadsto \ \ \) \(\displaystyle 3 \uparrow \paren {x + 16 m_1}\) \(=\) \(\displaystyle 3 \uparrow \paren {y + 16 m_2}\) Definition of $\phi$
\(\displaystyle \leadsto \ \ \) \(\displaystyle 3^x \paren {3^{16} }^{m_1}\) \(=\) \(\displaystyle 3^y \paren {3^{16} }^{m_2}\) Product of Powers, Power of Power
\(\displaystyle \leadsto \ \ \) \(\displaystyle 3^x \times 1^{m_1}\) \(=\) \(\displaystyle 3^y \times 1^{m_2}\) as $3^{16} = 1 \pmod {17}$ from $(1)$
\(\displaystyle \leadsto \ \ \) \(\displaystyle 3^x\) \(=\) \(\displaystyle 3^y\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle y\)

Thus $\phi$ is an injection.

From Equivalence of Mappings between Sets of Same Cardinality it follows that $\phi$ is a bijection.

$\Box$


Thus $\phi$ is a bijective group homomorphism.

Hence the result by definition of group isomorphism.

$\blacksquare$


Sources