Math 120A HW 5 Solutions
-
Let $i,j \in \mathbb{Z}_n$. We want to show that $\phi(i + j \bmod{n}) = \phi(i)\phi(j)$.
First, consider the case where $i+j \lt n$.
Then $\phi(i + j \bmod{n}) = a^{i + j \bmod{n}} = a^{i+j} = a^ia^j = \phi(i)\phi(j)$ as desired.
Second, consider the case where $i+j \ge n$. Then $\phi(i + j \bmod{n}) = a^{i + j \bmod{n}} = a^{i+j-n} = a^ia^j(a^n)^{-1} = a^ia^j = \phi(i)\phi(j)$ as desired. In the second case we used the fact that $a^n$ is the identity element of $G$, which follows from the fact that $n$ is the order of $G$ (and hence $n$ is also the order of $a$, because $a$ is a generator of $G$.)
-
Recall that an element of $\mathbb{Z}_n$ is a generator if and only if it is relatively prime to $n$.
In the present case $n =pq$ where $p$ and $q$ are distinct prime numbers, so the prime factors of $n$ are $p$ and $q$, and an element is relatively prime to $n$ if and only if it is divisible by neither $p$ nor $q$.
There are $q$ many elements of $\mathbb{Z}_{pq}$ that are divisible by $p$, namely $0,p,2p,\ldots,(q-1)p$.
There are $p$ many elements of $\mathbb{Z}_{pq}$ that are divisible by $q$, namely $0,q,2q,\ldots,(p-1)q$.
There is exactly $1$ element of $\mathbb{Z}_{pq}$ that is divisible by both $p$ and $q$, namely $0$ (because $p$ and $q$ are both prime, in particular they are relatively prime, so their least common multiple is $pq$.)
Therefore the number of elements of $\mathbb{Z}_{pq}$ that are divisible neither by $p$ nor by $q$ is $pq - p - q + 1$, which can be simplified to $(p-1)(q-1)$.
- Let $n,k \in \mathbb{Z}^+$.
Define a function $\phi:\mathbb{Z}_n \to \mathbb{Z}_n$ by $\phi(a) = ka$. Here
$ka$ means the $k^\text{th}$ multiple of $a$ in the sense of $\mathbb{Z}_n$,
which is equal to $\underbrace{a +_n \cdots +_n a}_{k \text{ times}}$.
However, note that we can equivalently define $ka$ in $\mathbb{Z}_n$ by multiplying $k$ and $a$ in the usual sense and only reducing modulo $n$ at the end.
-
Let $a,b \in \mathbb{Z}_n$. Then $\phi(a + b \bmod n) = k(a+b \bmod n)
\bmod n = k(a+b) \bmod n = ka + kb \bmod n = (ka \bmod n) + (kb \bmod
n) \bmod n = \phi(a) + \phi(b) \bmod n$. (Some of the instances of
"$\text{mod }n$" can be omitted if we understand multiplcation by
$k$ to be in the sense of $\mathbb{Z}_n$ rather than in the sense of
$\mathbb{Z}$, but it doesn't hurt to leave them in.)
-
Because $\mathbb{Z}_n$ is a finite set, it suffices to show that $\phi$ is
injective (then it must be surjective also by the pigeonhole principle.)
Let $a, b \in \mathbb{Z}_n$. If $\phi(a) = \phi(b)$, then $ka \bmod n =
kb \bmod n$, so the number $k(a-b)$, which is equal to $ka-kb$, is divisible by $n$.
Because $k$ is relatively prime to $n$, this implies that $a-b$ itself is
divisible by $n$. But $a,b \in \mathbb{Z}_n$, so this implies that $a =
b$ as desired.
- Here are the elements of $S_3$ and their orders. (You don't have
to name them, but doing so saves writing. I chose to use the names we
have been using for elements of the dihedral group $D_3$, because $S_n = D_n$ when $n=3$.)
- $\sigma_1 =
\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix}$. Because $\sigma_1$ is not the identity element, $\sigma_1^2 = \sigma_2$ is not the identity element, and $\sigma_1^3$ is the identity element, the order of $\sigma_1$ is $3$.
- $\sigma_2 =
\begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix}$. Because $\sigma_2$ is not the identity element, $\sigma_2^2 = \sigma_1$ is not the identity element, and $\sigma_2^3$ is the identity element, the order of $\sigma_2$ is $3$.
- $\sigma_3 =
\begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix}$. Because $\sigma_3$ is the identity element, its order is $1$.
- $\rho_1 =
\begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1 \end{pmatrix}$.
Because $\rho_1$ is not the identity element and $\rho_1^2$ is the identity element, the order of $\rho_1$ is $2$.
- $\rho_2 =
\begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix}$.
Because $\rho_2$ is not the identity element and $\rho_2^2$ is the identity element, the order of $\rho_2$ is $2$.
- $\rho_3 =
\begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3 \end{pmatrix}$.
Because $\rho_3$ is not the identity element and $\rho_3^2$ is the identity element, the order of $\rho_3$ is $2$.