Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
What should you work on?
- 94 - You are creating a collection of counterexamples.
- 95 - An interesting example that leads to more understanding of the Euler phi function.
- 96 - With 92 under your belt, you can quickly prove that the order of every subgroup divides the order of the group.
- 97 - Show that a few subgroups are normal, so show that $Ha=aH$ for every $a\in G$.
- 98 - MOST IMPORTANT PROBLEM. We need to see this before thanksgiving.
We need some more examples of homomorphisms. Simple shift permutations from cryptography provides us with quite a few. Make sure you can prove the following exercise.
Exercise (A Homomorphism From $\mathbb{Z}_n$ to $\mathbb{Z}_d$ when $d$ is a divisor of $n$)
Consider the map $f:\mathbb{Z}_{n}\to \mathbb{Z}_d$ defined by $f(x)=x\pmod d$ where $d$ is a divisor of $n$. Show that $f$ is a homomorphism.
Click to see a solution
We need to show that $((x+y)\pmod n)\pmod d = (x\pmod d+y\pmod d)\pmod d$. We know that $a\pmod d=b\pmod d$ if and only if $a-b$ is a multiple of $d$ (does this look like the coset property that says $Ha=Hb$ if and only if $ab^{-1}\in H$?). We just need to show that $(x+y)\pmod n - (x\pmod d+y\pmod d)$ is a multiple of $d$. To do this, first note that using the division algorithm we can write $x\pmod d = x-q_xd$ and $y\pmod d = y-q_yd$ for some integers $q_x$ and $q_y$, and we can write $(x+y)\pmod n = (x+y)-qn$ for some integer $q$. Since we know $d$ is a divisor of $n$, we can also write $n=md$ for some integer $m$. We then compute $$\begin{align} (x+y)\pmod n - (x\pmod d+y\pmod d) &=(x+y-qn)-(x-q_xd)-(y-q_yd)\\ &=-qmd+q_xd+q_yd\\ &=d(q_x+q_y-qm), \end{align}$$ which is a multiple of $d$ as desired.
What happens if $d$ is not a divisor of $n$? Does the map $f:\mathbb{Z}_n\to \mathbb{Z}_d$ defined by $f(x)=x\mod d$ result in a homomorphism?
Problem 94 (When is $x \pmod d$ a homomorphism from $\mathbb{Z}_n$ to $\mathbb{Z}_d$)
Let $G=\mathbb{Z}_{12}$ and $H=\mathbb{Z}_5$. Let $f:G\to H$ be the map defined by $f(x)=x\mod 5$.
- Is the map $f:G\to H$ a homomorphism? Either prove that it is, or produce a counter example.
- Let $n$ be an integer and suppose that the positive integer $d<n$ is not a divisor of $n$. Is the map $f:\mathbb{Z}_n\to \mathbb{Z}_d$ defined by $f(x)=x\mod d$ a homomorphism?
The problems above also give us homomorphisms from $U(n)$ to $U(d)$, as the next problem shows. These maps are crucial in understanding cryptography.
Problem 95 (The set $U_d(n)$ and the homomorphism from $U(n)$ to $U(d)$)
For each integer $n\geq 2$ and each divisor $d$ of $n$, consider the map $f:U(n)\to U(d)$ defined by $f(x)=x\pmod d$.
- Show that this map is a homomorphism. [Hint: You will probably want to use the fact that $a\pmod k=b\pmod k$ if and only if $a-b$ is a multiple of $k$. This is the easiest way to prove statements about modular arithmetic. You have to show that two things are equal, namely that $((x\cdot y)\pmod n)\pmod d = ((x \pmod d)\cdot (y \pmod d))\pmod d$. You can remove the outermost $\pmod d$ by instead showing that the difference is a multiple of $d$.]
- Then explain why the set $U_d(n)=\{x\in U(n)\mid x\pmod d = 1\}$ is a subgroup of $U(n)$. (Hint: What is the kernel of $f$?)
- List the elements of $U_{5}(60)$.
The next theorem should come as no surprise. We've already shown that given any subgroup $H$ of $G$, that every element of $H$ is in one of the cosets of $H$. We've also shown that the cosets of $H$ are disjoint. These two facts together show that we can partition $G$ into a disjoint union of cosets of $H$. We also know that the size of each coset matches the order of $H$. So if we have $r$ disjoint cosets $Ha_1$, $Ha_2$, $Ha_3$, ..., $Ha_r$, all of which have the same number of elements, then we should be able to use this information to show that the order of $H$ divides the order of the group. This fact is called Lagrange's theorem.
Problem 86 (Lagrange's Theorem Proof)
Prove Lagrange's Theorem.
Theorem (Lagrange's Theorem)
Suppose that $G$ is a finite group and that $H$ is a subgroup of $G$. Then the order of $H$ divides the order of $G$. In particular, we know that $|G|/|H|$ equals the number of distinct right (or left) cosets of $H$ in $G$.
We now have shown that the $|G|/|H|$ is precisely the number of cosets of $H$ there are in $G$. From a Cayley graph perspective, this is how many copies of $H$ are visible in the graph, as they are translated throughout the graph. The number of such cosets is called the index of $H$ in $G$, and written $|G:H|$.
Definition (Index of $H$ in $G$, or $|G:H|$)
If $H$ is a subgroup of $G$, then the index of $H$ in $G$, written $|G:H|$, is the number of distinct right (or left) cosets of $H$. Because of Lagrange's theorem, we know that $|G:H|=|G|/|H|$.
We'll now return to looking at when the left and right cosets of a subgroup agree, namely we'll be looking at normal subgroups. Let's first get ourselves a collection of subgroups that are normal.
Definition (Normal Subgroup $N\trianglelefteq G$)
We say that a subgroup $N$ of $G$ is a normal subgroup of $G$ if for each $a\in G$ the right coset $Na$ and left coset $aN$ are equal, so we have $Na=aN$ for every $a\in G$. We write $N\trianglelefteq G$ to mean that $N$ is a normal subgroup of $G$.
Problem 87 (Some Normal Subgroups)
Prove the following facts.
- If $G$ is Abelian, then every subgroup of $G$ is normal.
- The center $Z(G)$ of any group $G$ is always a normal subgroup of $G$.
We are now ready to define a new group using the cosets of a normal subgroup. If $N$ is a normal subgroup of $G$, then we've already shown that the binary operation on the collection of cosets, defined by $(Na)(Nb)=N(ab)$, is well defined. Is this binary operation enough to forma a group? To say yes, we need to show that the operation is associative, that there is there an identity coset, and that every coset has an inverse coset. We're now ready to prove that the collection of cosets of a normal subgroup is actually a group, and we call this the factor group of $G$ by $N$, or the quotient group of $G$ by $N$, and we write $G/N$ to talk about this group of cosets.
Definition (Factor Group or Quotient Group of $G$ by $N$, or $G/N$)
Let $G$ be a group. Let $N$ be a normal subgroup of $G$. Then we define the factor group of $G$ by $N$, or the quotient group of $G$ by $N$, to be the set $G/N = \{Na\mid a\in G\}$, i.e the collection of right cosets of $N$ using the set product $(Na)(Nb)=N(ab)$ as the binary operation.
Problem 88 (The Quotient Group $G/N$ Is A Group)
Let $G$ be a group and let $N$ be a normal subgroup of $G$. Prove that the set $G/N$ is actually a group under the operation of coset products.
For more problems, see AllProblems