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.
- 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