Tour:Mind's eye test four (beginners)

This page is a mind's eye test (more info), part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Factsheet four (beginners)| UP: Introduction four | NEXT: Hard nuts four (beginners)
PREVIOUS SECTION MIND'S EYE TEST: Mind's eye test three|NEXT SECTION MIND'S EYE TEST: Mind's eye test five
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

The notion of isomorphism

Isomorphism for other algebraic structures

Recall the following definitions:

• Magma: A set with a binary operation.
• Semigroup: A set with an associative binary operation.
• Monoid: A set with an associative binary operation having a two-sided identity element.

1. NEEDS SOME THOUGHT: An isomorphism between two magmas $(S,*)$ and $(T,\times)$ is a bijective map $\varphi:S \to T$ such that $\varphi(x * y) = \varphi(x) \times \varphi(y)$. An isomorphism class of magmas is an equivalence class of magmas under the relation of being isomorphic. Find all isomorphism classes of magmas with two elements.
2. NEEDS SOME THOUGHT: Prove that if two groups are isomorphic as magmas, then they are isomorphic as groups. Further, prove that if a group is isomorphic to a magma (as magmas) then the magma is also a group.
3. NEEDS SOME THOUGHT: Define the notion of isomorphism for semigroups and for monoids. Prove that if two monoids (resp., semigroups) are isomorphic as magmas, they are isomorphic as monoids (resp., semigroups). Further, prove that if a monoid (resp., semigroup) is isomorphic to a magma (as magmas) then the magma is also a monoid (resp., semigroup).

What isomorphisms do to elements

Isomorphisms preserve all properties. We see some special cases.

1. Prove that two isomorphic groups must have the same order.
2. Prove that any group isomorphic to an abelian group is abelian.
3. Prove that an isomorphism must preserve the order of each element. In other words, if $x$ has order $n$, so does the image of $x$ under the isomorphism.
4. Prove that, under an isomorphism, every subgroup gets mapped to an isomorphic subgroup.

Additive cyclic group

The group of integers: subgroups, containment, joins and intersections

For the purposes of these exercises, an ascending chain of subgroups is a chain of subgroups like:

$H_1 \le H_2 \le \dots \le H_n \le$

and a descending chain of subgroups is like:

$H_1 \ge H_2 \ge \dots \ge H_n \ge$

We say it is strictly ascending (resp. descending) if each $H_i$ is a proper subgroup of $H_{i +1}$ (resp., $H_{i+1}$ is a proper subgroup of $H_i$). The ascending chain is finite if it stops at some finite stage, and infinite if it goes on for all natural numbers.

1. Prove that any maximal subgroup of the group of integers (i.e., any proper subgroup not contained in any other proper subgroup) is generated by a prime number.
2. NEEDS SOME THOUGHT: Prove that if $n = p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}$, there is a strictly descending chain of subgroups of length $\sum_{i=1}^r k_i$, starting from $\mathbb{Z}$ and ending at $n\mathbb{Z}$. Hence prove that in the group of integers, there can exist a strictly descending chain of subgroups of infinite length.
3. NEEDS SOME THOUGHT: Prove that in the group of integers, the subgroup $n\mathbb{Z}$ has index $n$, and its cosets are the congruence classes modulo $n$. Hence, prove that in the group of integers, any nontrivial subgroup has finite index.
4. NEEDS SOME THOUGHT: Prove that in the group of integers, any ascending chain of subgroups has only finite length.

Finite cyclic groups

1. NEEDS SOME THOUGHT: Prove that for any natural number $n$, the cyclic group of order $n$ has precisely one subgroup of order $d$ for every divisor $d$ of $n$. Further, prove that this subgroup can be described as the set of multiples of $n/d$, and also as the set of elements whose order divides $d$.
2. Prove that if $a$ and $b$ are relatively prime, then in the cyclic group of order $ab$, the subgroups of order $a$ and order $b$ intersect trivially and together generate the whole group. (Hint: Once you know that cyclic subgroups of order $a$ and $b$ exist, the rest is achieved by Lagrange's theorem).
3. Let $p$ be a prime. Prove that any two subgroups of the cyclic group of order $p^k$ are comparable: one is contained in the other.

Unions of subgroups

In the exercises here, we'll assume the trivial group to be cyclic.

1. Prove that any finite group of order $n > 1$ is a union of at most $n - 1$ cyclic groups. (in mind's eye test three, we did a version of this: we prove that every group is a union of cyclic subgroups).
2. Prove that a group is cyclic if and only if it cannot be expressed as a union of proper subgroups. For full proof, refer: Cyclic iff not a union of proper subgroups
3. NEEDS LOT OF THOUGHT: Prove that if $G$ is any finite group, then we have the following identities, where the summation is over all cyclic subgroups $C$ of $G$, and $\sqcup$ stands for disjoint union.
   • $G = \bigsqcup_C \operatorname{Cyclic \ elements \ for \ } C$
   • $|G| = \sum_C \varphi(|C|)$
4. NEEDS SOME THOUGHT: Applying the above to a cyclic group of order $n$, prove that $n = \sum_{d|n} \varphi(d)$ (Hint: Use the fact that a cyclic group of order $n$ has exactly one subgroup of order $d$ for each $d | n$, and this subgroup is cyclic).

Generating sets

1. NEEDS SOME THOUGHT: Suppose $A$ is a subset of $\mathbb{Z}$. Prove that the subgroup generated by $A$ is the cyclic subgroup generated by the greatest common divisor of all elements of $A$.

Order and exponent

Warm-up

The exponent of a group is defined as the least common multiple of the orders of all elements; in other words, it is the smallest natural number $d$ such that $g^d$ is the identity element for all $g$ in the group. If no such $d$ exists, the group is said to have infinite exponent.

1. NEEDS SOME THOUGHT: Prove that the order of any element of a finite group divides the order of the group. (Hint: Prove that the order of the element equals the order of the cyclic subgroup it generates)
2. Prove that the exponent of a group divides the order of the group.
3. Prove that if a group has order $n$, then $g^n$ is the identity element for all $g$ in the group.
4. Prove that for a cyclic group, the order equals the exponent.
5. Let $p$ be a prime and $k$ be a natural number. Prove that if a group of order $p^k$ is not cyclic, its exponent cannot equal its order.

Power maps

Recall that we saw in the tour that if $k$ and $n$ are relatively prime integers, there exist integers $a,b$ such that $ak + bn = 1$.

1. NEEDS LOT OF THOUGHT: Prove that if $k$ is relatively prime to the order of a finite group $G$, the map $g \mapsto g^k$ is a bijective map from $G$ to itself. For full proof, refer: kth power map is bijective iff k is relatively prime to the order

Relation with cosets

1. Suppose $G$ is a nontrivial group of exponent two. Prove that any subset of $G$ of size two is a left coset of some subgroup.
2. Suppose $G$ is a nontrivial group of exponent three: every non-identity element has order three. Prove that for any two distinct elements $a,b \in G$, there exists a unique element $c \in G$ such that $\{ a,b,c \}$ is a left coset. Obtain an expression for $c$ in terms of $a$ and $b$. (Note: This is related to the game of SET; in fact, an analogue to the game of SET can be constructed on any group of exponent three)

Intersections and joins

1. Suppose $H,K$ are subgroups of a finite group $G$. Prove that the exponent of $H \cap K$ divides the greatest common divisor of the orders of $H$ and $K$. Further, prove that the exponent of $\langle H, K \rangle$ is a multiple of the last common multiple of the exponents of $H$ and $K$.
2. Prove that if $H,K$ are subgroups of $G$ such that both $H$ and $K$ have finite exponent, and these exponents are relatively prime, then $H \cap K$ is the trivial subgroup.

Multiplicative group and modular arithmetic

1. Prove Fermat's little theorem: For any prime $p$ and any integer $a$ that is not a multiple of $p$, $p$ divides $a^{p-1} - 1$. (Hint: Use Lagrange's theorem on the multiplicative group)
2. Prove Euler's theorem: For any positive integer $n$ and any integer $a$ relatively prime to $n$, $n$ divides $a^{\varphi(n)} - 1$. (Hint: Use Lagrange's theorem on the multiplicative group). For any positive integer $n$, let $\lambda(n)$ denote the exponent of the multiplicative group mod $n$. Reformulate the above statement as: $\lambda(n)|\varphi(n)$ for any $n$.
3. A positive integer $n$ is termed pseudoprime to base $a$ if $a$ and $n$ are relatively prime, and $n$ divides $a^{n-1} - 1$. For any positive integer $n$, let $H_n$ be the set of all congruence classes of $a$ mod $n$ for which $n$ is pseudoprime to base $a$. Prove that $H_n$ is a subgroup of the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^*$ mod $n$.
4. Following notation from the previous problem, prove that $H_n$ is the whole multiplicative group mod $n$ if and only if $\lambda(n) | n - 1$. In either of these equivalent circumstances, we say that $n$ is an absolute pseudoprime.
5. Prove that if $n$ is not an absolute pseudoprime, then the probability that $n$ is pseudoprime to a base $a$ picked uniformly at random on $\{ 1,2,3, \dots, n \}$, is less than 1/2. (Hint: Recall from Mind's eye test three that subgroup of size more than half is whole group)

This page is a mind's eye test (more info), part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Factsheet four (beginners)| UP: Introduction four | NEXT: Hard nuts four (beginners)
PREVIOUS SECTION MIND'S EYE TEST: Mind's eye test three|NEXT SECTION MIND'S EYE TEST: Mind's eye test five
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part