Problem-solving recipes

A step-by-step procedure for every problem type this course teaches — what to do first, what to do next, and how to tell which case you're in.

What are you being asked to do?

Start with what you're actually being asked to produce.

A relation to check, or a division to carry out — readiness review: check a relation and find its classes, or find q and r from the division algorithm.

A group's identity or an inverse — find the identity and an element's inverse.

A single element's behavior — its order, an integer power of it, or every generator of the cyclic group it generates.

Arithmetic in $\mathbb{Z}_n$ or $U(n)$ — add two elements, decide whether one is a unit, run the Euclidean algorithm and Bezout's identity, compute Euler's phi, find the generators of $\mathbb{Z}_n$ , apply the classification theorem to a finite cyclic group, or compute a modular power by repeated squaring — in that rough dependency order.

A permutation — compose two of them, determine one's parity, or list every element of $A_n$ .

An element of $D_n$ — list every element of $D_n$ , or compare $r \circ s$ to $s \circ r$ .

A subgroup — find the cyclic subgroup an element generates, or find every subgroup of a finite cyclic group.

A coset — compute one directly from its elements.

Conjugation, the center, or the normalizer — compute a single conjugate, find the center of a group, find the normalizer of a subgroup, or build a non-normal subgroup by conjugating a point-stabilizer.

A quotient group — build $G/N$ from scratch, or build the quotient of an index-2 subgroup without a full table.

Readiness review

Check a relation and find its classes

Use when: you're handed a specific relation on a set and need to know whether it's an equivalence relation, and if so, what its classes are

Goal: either a confirmed equivalence relation with its full list of classes, or the specific property that fails

Equivalence relations and partitions, revisited

Find q and r from the division algorithm

Use when: you have integers $a$ and a positive $b$ and need the unique $q$ , $r$ with $a = bq + r$ and $0 \le r < b$

Goal: the exact quotient and remainder pair guaranteed by the division algorithm, even when $a$ is negative

Divisibility and the division algorithm, revisited

Foundations

Find the identity and an element's inverse

Use when: you have a set with an operation and need the identity element, or a specific element's inverse under that operation

Goal: the identity element (if one exists) and the inverse of a given element (if it exists)

Identity and inverses

Basic group concepts

Compute the order of an element

Use when: you have one specific element $a$ of a group and need the smallest $n$ with $a^n = e$

Goal: the order of $a$ , a single positive integer, or the conclusion that $a$ has infinite order

Order of an element

Compute $a^n$ for any integer $n$

Use when: you need a specific integer power of a group element, and the exponent $n$ could be positive, zero, or negative

Goal: the single element $a^n$ , computed correctly regardless of the sign of $n$

Powers and integer exponents of an element

Builds on an element's order from the recipe above to reduce large exponents.

Find every generator of a finite cyclic group

Use when: you have a finite cyclic group of order $n$ and need every element that generates it, not just one

Goal: the complete, exact list of generators, or the conclusion that the group has none

Generators of a cyclic group

Modular arithmetic and cyclic groups

Add two elements in $\mathbb{Z}_n$

Use when: you need $a+b$ inside $(\mathbb{Z}_n, +)$ , including finding an additive inverse or filling in one cell of a Cayley table

Goal: the single representative in $\{0,\ldots,n-1\}$ that $a+b$ actually equals, with the wraparound step never skipped

The group Z_n under addition

Compute gcd(a, b) and Bezout's x, y with the Euclidean algorithm

Use when: you're given two positive integers a and b and need gcd(a, b), or integers x, y with ax + by = gcd(a, b)

Goal: the greatest common divisor of a and b, and, if needed, integers x and y expressing it as ax + by

The greatest common divisor and group structure

Decide whether a is a unit mod n by direct search

Use when: you're given one specific residue $a$ mod $n$ and need to know whether it has a multiplicative inverse, before the gcd shortcut is available

Goal: a decision, unit or not a unit, and if it is, the actual inverse $b$

Units modulo n and the group U(n)

Uses the Euclidean algorithm above to explain why a collision means no inverse.

Compute Euler's phi of n

Use when: you need $\varphi(n)$ , the count of integers from $1$ to $n$ coprime to $n$ , for a specific $n$

Goal: the exact value of $\varphi(n)$ , computed without listing or testing every candidate

Euler's phi function

Determine or list the generators of Z_n

Use when: you're asked whether one specific $k$ generates $\mathbb{Z}_n$ , or asked for the complete list of generators, or asked only how many there are

Goal: a definitive answer, generator or not for one $k$ , the full list, or the exact count, matching what was actually asked

Generators of Z_n

Use the classification theorem on a finite cyclic group

Use when: you have a cyclic group of known order $n$ and need to match it to $\mathbb{Z}_n$ by exponent, or find its subgroups by divisor

Goal: either the explicit exponent correspondence to $\mathbb{Z}_n$ , or the complete, correctly-sized list of subgroups

Classifying finite cyclic groups

Compute a^b mod n by repeated squaring

Use when: you need $a^b \bmod n$ for an exponent $b$ too large to multiply out one factor at a time by hand

Goal: the value of $a^b \bmod n$ , computed with only about $\log_2 b$ multiplications

A first look at modular exponentiation

Permutation groups

Compute the composition of two permutations

Use when: you're given two permutations $\sigma$ and $\tau$ , in two-line or cycle notation, and need $\sigma\circ\tau$

Goal: the resulting permutation $\sigma\circ\tau$ , written out in cycle notation

Composing permutations

Determine the parity of a permutation

Use when: you have a permutation, given as one or more cycles (disjoint or not), and need to classify it as even or odd

Goal: a definitive even-or-odd classification, reached from cycle lengths alone

Parity -- even and odd permutations

Needs a permutation's disjoint-cycle decomposition, from composing permutations above.

List every element of A_n

Use when: you need every element of the alternating group A_n for a small n, not just a verdict on one permutation

Goal: a complete, non-redundant list of A_n's n!/2 elements, organized by cycle type

The alternating group Aₙ

Needs parity, from the recipe above, to keep only the even permutations.

Dihedral and symmetry groups

List every element of D_n

Use when: you're given a regular n-gon, or just its symmetry count 2n, and need every element of D_n written with the r^k / r^k s labels

Goal: a complete list of D_n's 2n elements, split into n rotations and n reflections

The dihedral group Dₙ

Compare r∘s to s∘r in D_n

Use when: you're given the two generators r and s of D_n and must find s∘r's label, or check whether r and s commute

Goal: both composition orders written as single labeled elements, and a verdict on whether they're equal

Composing symmetries and non-abelian behavior

Subgroups

Find the cyclic subgroup generated by an element

Use when: you're given a specific element g of a group and asked for the entire cyclic subgroup ⟨g⟩ it generates

Goal: either the complete finite list of ⟨g⟩'s elements, or a correct description of its infinite structure

Cyclic subgroups, revisited

Find the subgroups of a finite cyclic group

Use when: you have a cyclic group G=⟨g⟩ of known finite order n and need one or all of its subgroups

Goal: the exact subgroup(s) of G, each one correctly matched to a divisor of n, with no missing or extra orders

Subgroups of cyclic groups

Extends the recipe above from one generator's subgroup to all of them, by divisor.

Cosets and Lagrange's theorem

Compute a coset of a subgroup

Use when: you're given a subgroup H, a representative g, and a side (left or right), and asked for the coset gH or Hg

Goal: the complete coset as a set of |H| elements, with none skipped and none miscomputed

Left and right cosets

Normal subgroups

Compute a conjugate ghg⁻¹

Use when: you're given specific elements $g$ and $h$ of a group and asked to compute the single element $ghg^{-1}$

Goal: the element $ghg^{-1}$ , simplified to the group's own standard notation

Conjugation

Find the center of a group

Use when: you're given a specific group $G$ with a known generating set and asked for every element that commutes with all of $G$

Goal: the complete set $Z(G)$ , confirmed one candidate at a time

The center of a group

Tests every generator by conjugation, from the recipe above.

Find the normalizer of a subgroup

Use when: you're given a subgroup $H\le G$ with a known generating set and asked for every $g\in G$ satisfying $gHg^{-1}=H$

Goal: the complete set $N_G(H)$ , and whether it equals $H$ , $G$ , or something strictly between

The normalizer of a subgroup

Also built on conjugation, testing whether it fixes H as a set rather than fixing each element.

Build a non-normal subgroup by conjugating a point-stabilizer

Use when: you're inside some $S_n$ with $n\ge3$ and asked to produce a subgroup that isn't normal, or to test whether a 'fixes one point' subgroup is normal

Goal: an explicit point-stabilizer $H$ together with one concrete permutation proving $gHg^{-1}\ne H$

Normal subgroups: examples and counterexamples

Uses conjugation to produce the counterexample that proves normality can fail.

Quotient groups

Build the quotient group G/N

Use when: you're given a group $G$ and a confirmed normal subgroup $N$ , and need $G/N$ 's elements, its operation, or a specific identity or inverse inside it

Goal: every coset of $N$ , the operation between any two of them, and $G/N$ 's identity and inverses

The quotient group G/N

Build the quotient group of an index-2 subgroup

Use when: you're given a subgroup $H$ with $[G:H]=2$ , exactly two cosets, and need both a normality proof and a description of $G/H$

Goal: a proof that $H$ is normal, plus the complete operation table of the two-element group $G/H$

Quotient groups of permutation groups

A shortcut on the recipe above for the common index-2 case, avoiding a full table.