Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
Every time you seen an Exercise in the problem set, you should spend a couple minutes trying to answer the question. These questions are designed as a quick check of some facts that you should be familiar with. Come up with a solution, and then click to see the solution.
Exercise (What Is The Group Operation On The Integers)
If we want to consider $\mathbb{Z}$ as group, then which operation do we use, addition or multiplication? Why? Which is a group, is it $(\mathbb{Z},+)$ or is it $(\mathbb{Z},\cdot)$?
Click to see a solution.
The integers are a group under addition (the sum of two integers is an integer, the identity is 0, the inverse of $n$ is $-n$, and addition is associative as an axiom). For multiplication, the inverse of $2$, which is $1/2$, is not an integer so $\mathbb{Z}$ is not closed under inverses. There is no multiplicative inverse of 0 as $0x\neq 1$ for any integer $x$.
Exercise (Are The Natural Numbers A Subgroup Of The Integers)
Is $\mathbb{N}$ closed under the operation of addition? Is $\mathbb{N}$ a subgroup of $\mathbb{Z}$?
Click to see a solution.
The sum of two positive integers is a positive integer, so $\mathbb{N}$ is closed under the operation of $\mathbb{Z}$ (which is addition). However, the inverse of $2$ under addition is $-2$, but $-2\notin \mathbb{N}$. This shows that $\mathbb{N}$ is not closed under taking inverses, and hence is not a group (so not a subgroup of $\mathbb{Z}$).
We'll start today by showing that if $H$ is a nonempty finite subset of a group that is closed under the operation, then it automatically is a subgroup. You should find that your work from the problem The Inverse In A Finite Group Is A Power Of The Element should help. Remember, the key was to consider the sequence $a, a^2, a^3, a^4, \ldots$ which cannot consist of all different elements, which means there must be $i,j\in \mathbb{Z}$ with $a^i=a^j$ and $j>i$. Try repeating the argument almost exactly, but this time pay attention to what happens if $j-i-1=0$.
Problem 53 (Finite Subgroup Test)
Let $G$ be a group. Suppose that $H$ is a nonempty finite subset of $G$ and that $H$ is closed under the operation of $G$ (so if $a,b\in H$, then we must have $ab\in H$). Prove that $H$ is a subgroup of $G$.
Take a moment to reread the problem The Span Of A Simple Shift. In this problem, we looked at the span of various simple shift permutations. We saw many patterns that we conjectured without proof. In particular, we noticed that two simple shifts $\phi_i$ and $\phi_j$ had the same span if they had the same greatest common divisor with 12 (the size of the alphabet). It's time to prove this conjecture, as well as many more.
The following problem requires that you use the GCD theorem. If you let $d=\gcd(n,k)$, then remember that there are integers $s$ and $t$ such that $d=sn+tk$. This will be your key tool in working with the greatest common divisor.
Problem 62 ($\langle a^k\rangle = \langle a^{\gcd(k,|a|)}\rangle$)
Let $a$ be an element of order $n$ and let $k\in\mathbb{N}$. Prove that $\langle a^k\rangle = \langle a^{\gcd(k,n)}\rangle$.
You'll need to use the definition of order, and two previos problems to make short work of this problem. In particular, if you pay attention to the fact that the order of an element always matches the order of the subgroup generated by that element, then you can make sense of $|a^k|$ in terms of a greatest common divisor.
Problem 63 ($|a^k| = |a|/\gcd(k,|a|)$)
Let $a$ be an element of order $n$.
- If $d$ is a divisor of $n$, then prove that $|a^d|=n/d$.
- For any $k\in \mathbb{N}$, prove that $|a^k| = n/\gcd(k,n)$.
The previous two problems are the key tools to unlocking all of our other conjectures about simple shift permutations. In particular, the order of a simple shift permutation on $n$ letters will always be a divisor of $n$. Let's first make a new definition, a cyclic group, to generalize any group that behaves like the simple shift permutations.
Definition (Cyclic Group)
Let $G$ be a group. If there exists an element $a\in G$ such that $\langle a\rangle=G$, then we say that $G$ is a cyclic group.
Problem 64 ($\langle a^i \rangle = \langle a^j \rangle$ iff $\gcd(i,n)=\gcd(j,n)$)
Let $G$ be a group. Suppose that $a\in G$ has order $n>1$. Prove the following two facts:
- If $G$ is a cyclic group, then the order of $a$ divides the order of the group.
- We have $\langle a^i \rangle = \langle a^j \rangle$ if and only if $\gcd(i,n)=\gcd(j,n)$.
Click for a hint.
- If $G$ is cyclic, then pick a generator, say $b$. This means $G=\langle b\rangle$. Why does this mean $a=b^k$ for some $k$? Use this to show that $b$ has finite order, say $m$. Then use problem 63 with $b^k$, where $|b|=m$, rather than $a^k$ and $|a|=n$.
- Problem 63 will get you one direction, and problems 62 will get you the other.
The second fact proves the following three corollaries by letting $i=1$.
- We have $\langle a \rangle = \langle a^j \rangle$ if and only if $\gcd(n,j)=1$.
- A simple shift permutation $\phi_j$ on $n$ letters generates all simple shift permutations on $n$ letters if and only if $\gcd(n,j)=1$.
- An integer $j\in \mathbb{Z}_n$ is a generator of $\mathbb{Z}_n$ if and only if $\gcd(n,j)=1$.
What does this have to do with the problem When Does An Integer Have A Modular Multiplicative Inverse? You should see a connection between this problem and elements of $U(n)$.
Exercise (Cyclic Groups Are Abelian)
Suppose that $G$ is a cyclic group. Prove that $G$ is an Abelian group.
Click to see a solution.
Since $G$ is cyclic, we know that there exists some $a\in G$ with $\langle a\rangle = G$. Let $x,y\in G$. We need to show that $xy=yx$. But we know that $x=a^m$ and $y=a^n$ for some $n,m\in \mathbb{Z}$ because $G$ is cyclic. This means that $$xy=a^ma^n=a^{m+n}=a^{n+m}=a^na^m=yx,$$ which is what we needed to show.
For more problems, see AllProblems