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
Contents
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.
- NEEDS SOME THOUGHT: An isomorphism between two magmas
and
is a bijective map
such that
. 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.
- 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.
- 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.
- Prove that two isomorphic groups must have the same order.
- Prove that any group isomorphic to an abelian group is abelian.
- Prove that an isomorphism must preserve the order of each element. In other words, if
has order
, so does the image of
under the isomorphism.
- 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:
and a descending chain of subgroups is like:
We say it is strictly ascending (resp. descending) if each is a proper subgroup of
(resp.,
is a proper subgroup of
). The ascending chain is finite if it stops at some finite stage, and infinite if it goes on for all natural numbers.
- 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.
- NEEDS SOME THOUGHT: Prove that if
, there is a strictly descending chain of subgroups of length
, starting from
and ending at
. Hence prove that in the group of integers, there can exist a strictly descending chain of subgroups of infinite length.
- NEEDS SOME THOUGHT: Prove that in the group of integers, the subgroup
has index
, and its cosets are the congruence classes modulo
. Hence, prove that in the group of integers, any nontrivial subgroup has finite index.
- NEEDS SOME THOUGHT: Prove that in the group of integers, any ascending chain of subgroups has only finite length.
Finite cyclic groups
- NEEDS SOME THOUGHT: Prove that for any natural number
, the cyclic group of order
has precisely one subgroup of order
for every divisor
of
. Further, prove that this subgroup can be described as the set of multiples of
, and also as the set of elements whose order divides
.
- Prove that if
and
are relatively prime, then in the cyclic group of order
, the subgroups of order
and order
intersect trivially and together generate the whole group. (Hint: Once you know that cyclic subgroups of order
and
exist, the rest is achieved by Lagrange's theorem).
- Let
be a prime. Prove that any two subgroups of the cyclic group of order
are comparable: one is contained in the other.
Unions of subgroups
In the exercises here, we'll assume the trivial group to be cyclic.
- Prove that any finite group of order
is a union of at most
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).
- 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
- NEEDS LOT OF THOUGHT: Prove that if
is any finite group, then we have the following identities, where the summation is over all cyclic subgroups
of
, and
stands for disjoint union.
-
- NEEDS SOME THOUGHT: Applying the above to a cyclic group of order
, prove that
(Hint: Use the fact that a cyclic group of order
has exactly one subgroup of order
for each
, and this subgroup is cyclic).
Generating sets
- NEEDS SOME THOUGHT: Suppose
is a subset of
. Prove that the subgroup generated by
is the cyclic subgroup generated by the greatest common divisor of all elements of
.
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 such that
is the identity element for all
in the group. If no such
exists, the group is said to have infinite exponent.
- 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)
- Prove that the exponent of a group divides the order of the group.
- Prove that if a group has order
, then
is the identity element for all
in the group.
- Prove that for a cyclic group, the order equals the exponent.
- Let
be a prime and
be a natural number. Prove that if a group of order
is not cyclic, its exponent cannot equal its order.
Power maps
Recall that we saw in the tour that if and
are relatively prime integers, there exist integers
such that
.
- NEEDS LOT OF THOUGHT: Prove that if
is relatively prime to the order of a finite group
, the map
is a bijective map from
to itself. For full proof, refer: kth power map is bijective iff k is relatively prime to the order
Relation with cosets
- Suppose
is a nontrivial group of exponent two. Prove that any subset of
of size two is a left coset of some subgroup.
- Suppose
is a nontrivial group of exponent three: every non-identity element has order three. Prove that for any two distinct elements
, there exists a unique element
such that
is a left coset. Obtain an expression for
in terms of
and
. (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
- Suppose
are subgroups of a finite group
. Prove that the exponent of
divides the greatest common divisor of the orders of
and
. Further, prove that the exponent of
is a multiple of the last common multiple of the exponents of
and
.
- Prove that if
are subgroups of
such that both
and
have finite exponent, and these exponents are relatively prime, then
is the trivial subgroup.
Multiplicative group and modular arithmetic
- Prove Fermat's little theorem: For any prime
and any integer
that is not a multiple of
,
divides
. (Hint: Use Lagrange's theorem on the multiplicative group)
- Prove Euler's theorem: For any positive integer
and any integer
relatively prime to
,
divides
. (Hint: Use Lagrange's theorem on the multiplicative group). For any positive integer
, let
denote the exponent of the multiplicative group mod
. Reformulate the above statement as:
for any
.
- A positive integer
is termed pseudoprime to base
if
and
are relatively prime, and
divides
. For any positive integer
, let
be the set of all congruence classes of
mod
for which
is pseudoprime to base
. Prove that
is a subgroup of the multiplicative group
mod
.
- Following notation from the previous problem, prove that
is the whole multiplicative group mod
if and only if
. In either of these equivalent circumstances, we say that
is an absolute pseudoprime.
- Prove that if
is not an absolute pseudoprime, then the probability that
is pseudoprime to a base
picked uniformly at random on
, 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