Final review

The midterm will take place on Tuesday, December 11, at 9am. No notes, no calculators, no textbooks.

This page will contain a brief overview of the material covered this semester, in the order given in Goren's notes. For a listing of the types of problems likely to be encountered on the final, along with guided general solutions and links to examples, see the "How to solve every problem" guide for the final.

1Arithmetic in the integers¶

Division with remainder. The "divides" relation.

GCD, and Bezout's identity. Proof: using the well-ordering principle (the minimal element of a set) and proof by contradiction.

Euclid's lemma: if $a \mid bc$ and $\gcd(a, b) = 1$, then $a \mid c$. Alternately: if a prime $p$ divides $ab$, then it divides $a$ or $b$. Proof: using Bezout's identity.

Euclidean algorithm: divide by the previous remainder. When the remainder is 0, the previous remainder is the gcd. Proof: by induction. Using the Euclidean algorithm to find $u, v$ in Bezout's identity: rearrange the equations. Keep the last non-zero remainder (the gcd) on one side.

Fundamental theorem of arithmetic: any non-zero integer can be uniquely factored as a product of primes. Proof of existence: well-ordering principle, contradiction (assume that the set of numbers that can't be written as a product of primes is not empty, so there's a minimal element that is composite, etc). Proof of uniqueness: by induction, making use of the fact that $p$ is prime $\iff$ ($p \mid ab \to p \mid a$ or $p \mid b$); we impose an ordering on two prime factorisations, then show that they are equal.

Infinitely many primes: by contradiction. Assume that you can enumerate all the primes (order them). Then their product + 1 is greater than the largest prime, and so it can't be prime. But it is, because the gcd of it and any other prime is 1.

Proof that $\sqrt{2}$ is irrational: using the FTA, we can try to write it as the product of primes. Then, square both sides, and since 2 is prime, we get that there is one prime (2) and its exponent is 1/2, which is impossible. (The other proof uses divisibility by 2 and stuff but apparently the first proof is nicer.)

2Congruences and modular arithmetic¶

Equivalence relations: reflexive, transitive, symmetric. Two equivalence classes are eitehr disjoint or equal, and their disjoint union forms the whole set.

$\mathbb Z/n\mathbb Z$ is a field if and only if $n$ is prime. Proof: need to show that if it's prime, every element has an inverse. Then we list $n+1$ elements ($\{1, a, a^2, \ldots, a^n\}$) and since at least two of them are the same, we have that $a^i = a^j$, then divide both sides by $a^j$, and that's equal to 1. So every element has an inverse! If it's not prime, then there are zero divisors, and so we get a contradiction.

Fermat's little theorem: $a^p = a \pmod p$. Proof: first prove a lemma showing that $p$ divides the binomial coefficient ($p$ on top, anything from 1 to $p$ on the bottom). Then, prove the theorem itself by induction.

Wilson's theorem (not in notes): $p$ is prime $\iff$ $p \mid (p-1)! + 1$. Proof for $\to$: assume $p$ is prime. Then $x^2=1\pmod p$ has solutions 1, -1. So 1 and -1 are their own inverses. Then if we look at the expanded version of $(p-1)!$ we see that everything has an inverse except $p-1$, which is incidentally equal to -1 mod p. So $(p-1)! = -1 \pmod p$. Then, yeah. For the other direction: prove the contrapositive, get a contradiction.

3Polynomials and their arithmetic¶

GCD. Monic polynomial of largest degree.

Irreducible: same as prime. All linear polynomials are.

Roots: correspond to factors. Everything is a root for $x^p - x \pmod p$ by FLT.

4Rings¶

Ring. Has addition and multiplication. Addition: assoc, commut, identity, inverse; multiplication: assoc, identity; distributivity. If it's a commutative ring, then multiplication is commutative as well. If it's a field, there there exist multiplicative inverses for all non-zero elements. Matrices (n by n) form a ring, but not a commutative or division ring.

The ring of dual numbers. $\epsilon^2=0$. $\epsilon$ is obviously a zero divisor. Every element in the form $a + b\epsilon$ where $a \neq 0$ has an inverse.

Subring. Properties: contains 0 and 1, closed under addition, closed under multiplication. Subrings are of course rings. Examples: $\mathbb Q \subseteq \mathbb R$.

Ideals. $0 \in I$, closed under ideal addition, closed under ring multiplication. The trivial ideals are $\{0\}$ and the whole ring. In a division ring, any ideal is trivial. Why? Well, if we multiply an element by its inverse, we get 1, which must be in the ideal. Then if 1 is in the ideal, everything is (due to closure under ring multiplication).

Principal ideals. In a commutative ring only. If every ideal is principal in this ring, it's a principal ideal ring (didn't see that coming). Example: $\mathbb Z$. Proof: the ideals are just $(0), (1), (2)$, which we can show using division with remainder (conclude that $r=0$, etc). Another example: the ring of dual numbers. The ideals are $(0), (1), (\epsilon)$.

Two ideals generated by polynomials in the principal ideal ring $\mathbb F[x]$ are equal if and only if the polynomials are equal. Proof: division with remainder.

Homomorphisms. Preserves the identity, addition, multiplication. The image of a homomorphism is always a subring of the target ring.

Kernel of a homormophism. This is an ideal, and the homo is injective iff the ideal is (0).

Units. Denoted $R^{\times}$. Elements with an inverse. In a field, this is all the non-zero elements. Closed under multiplication.

Cosets. $a + I = \{a + i: i \in I\}$. Every element belongs to a coset, and two cosets are either equal or disjoint. In fact, the entire ring is a disjoint union of cosets (there is in fact an equivalence relation associated with this).

Quotient rings. Modding out by an ideal. $\mathbb Z / (0)$ (the trivial ideal) then this is just isomorphic to $\mathbb Z$.

Modding out by an irreducible polynomial results in a field. Proof: Bezout's identity, gcd is 1, from this we can find an inverse for any non-zero element.

Creating finite fields. In fact, any finite field has cardinality $p^a$ where $p$ is some prime. (Not proved here.) To create, work in $\mathbb Z / p\mathbb Z$ and pick an irreducible polynomial of degree $a$.

Every polynomial has roots in a bigger field.

Isomorphism is an equivalence relation on rings!!! Verify the properties if you wish.

The first isomorphism theorem: $f: R \to S$ is a surjective homo, $I = \ker(f)$. Then $R/I \cong S$. Proof: define a new function making use of $f$, and verify that it is an isomorphism.

The Chinese remainder theorem. If $\gcd(m, n) = 1$, then $\mathbb Z / mn \mathbb Z \cong \mathbb Z / m \mathbb Z \times \mathbb Z / n\mathbb Z$. Proof: define a function taking $a$ to $(a\mod m, a\mod n)$ and prove that it is a bijective ring homo.

Maximal ideal: no ideals between it and $R$ (and not $R$). Prime ideal: $ab \in I$ implies $a \in I$ or $b \in I$. Prime ideals $\iff$ integral domains, maximal ideals $\iff$ the corresponding quotient ring is a field. Maximal ideals are prime ideals (but not vice versa, except in some cases).

5Groups¶

Definition: non-empty set with an operation. Properties: associativity, identity, inverse. Trivial group: just the identity, multiplication law. Ring of units: a group.

Subgroup: subset of a group with the identity, closure under multiplication, and existence of inverses. Also a group. Example: in $\mathbb C^{\times}$, the subset of all complex numbers of absolute value 1.

Cyclic group: if there is an element $g$ that functions as a generator, such that any element in the group can be expressed as a power of $g$. Examples: $\mathbb Z$ under addition, with 1 or -1 as a generator; $\mathbb Z/p \mathbb Z$ (not cyclic for non-prime $p$).

Permutation groups: $S_n$, with $n$ letters and cardinality $n!$. This is a group under (right-to-left) function composition.

Order of a group: number of elements in that group. Order of an element: the order of the cyclic group generated by $g$. Of course, if the element is a generator, it will be the same as the order of the group. Otherwise, it will be less (for the identity, it's 1). Incidentally, the order $k = \text{ord}(g)$ is also the least positive integer such that $g^k = e$. Proof of this: write out the first $k + 1$ elements, conclude that there is a duplicate, do the $g^{i-j} = 1$ trick for one direction, use division with residue for the exponent for the other direction.

Cycles: any permutation can be decomposed into cycles. A 2-cycle is called a transposition. The order of a cycle is its length. Two cycles are disjoint if they don't contain common elements. The order of a composition of disjoint cycles is their lcm. We can write any permutation as a composition of disjoint cycles.

Dihedral groups: a polygon, with all the rotations that preserve its shape. For a square, there are 8 ($D_8$): identity, rotation by 90/180/270 degrees, and the four reflections. If $x$ is a reflection and $y$ is a rotation, then we have that $x^2 = y^n = 1$ and $xyxy=1$. $D_n$ has $2n$ elements.

Cosets. A left coset of subgroup $H < G$ is given by $gH = \{gh: h \in H\}$. $g$ is the representative of the coset $gH$. Two cosets are either equal or disjoint. Also, the following are equivalent: $g_1H = g_2H$; $g_1 \in g_2H$; $g_2^{-1}g_1 \in H$. $G$ is a disjoint union of cosets. Note that in non-abelian groups, the intersection of the left and right cosets may not be a coset itself.

Lagrange's theorem: $|H|$ divides $|G|$. Also, the cardinality of a complete set of representatives for the cosets has cardinality $|G|/|H|$, and this number is called the index of $|H|$ in $|G|$. Proof: we show that every coset has the same number of elements by creating a bijection $f: aH \to bH$, $x \mapsto ba^{-1}x$, and since $eH = H$ is a coset, then $|G| = |H| \cdot |I|$.

Applications of Lagrange's: a finite group of prime order $p$ is cyclic, for the order of the subgroup generated by any element (other than the identity) must be $p$ (since it's greater than 1). So any element other than the identity generates the entire group!

Group homomorphism: $G$ and $H$ are homomorphic if there is a function $f: G \to H$ that respects the group operations, i.e., $f(g_1g_2) = f(g_1)f(g_2)$ for all $g_1, g_2 \in G$. The kernel of $f$ is everything in $G$ that is mapped to the identity, and is in fact a subgroup. $f$ is injective if and only if the kernel is trivial.

Isomorphism: Any two cyclic groups, $G$ and $H$, of order $n$ are isomorphic. Proof: define $f: G \to H$ with $f(g^a) = h^a$ where $a$ is some integer, show that it's well-defined, use division by remainder for the exponents to show that it's a surjective homomorphism, then show injectivity. In fact, any cyclic group of order $n$ is isomorphic to $(\mathbb Z/n\mathbb Z, +)$. (Note that $\mathbb Z/n\mathbb Z$ when $n$ is not prime is not a cyclic group.)

Normal subgroup: $gH = Hg$ for every $g \in G$ makes the subgroup $H$ normal. We could also write this as $gHg^{-1} = H$, so, $ghg^{-1} \in H$ for all $g \in G$, $h\in H$. The kernel of a group homomorphism is always a normal subgroup. Proof: let $h \in \ker(f)$, $g \in G$. $f(ghg^{-1}) = f(g)f(h)f(g^{-1}) = f(g)e f(g^{-1}) = f(g)f(g^{-1}) = f(gg^{-1}) = f(e) = e$. In an abelian group, all subgroups are normal.

Quotient groups. $G/H$ where $G$ is a group and $H$ is a normal subgroup of $G$. This is the collection of left cosets of $H$.

The first isomorphism theorem for groups. If $f: G \to H$ is a surjective group homo, then there is an isomorphism from $G/\ker(f) \to H$. Proof: define a function $g$ that maps $[a]$ to $f(a)$. This is well defined, because if $[a] = [b]$ then $b^{-1}a \in \ker(f)$ so it's okay. It's a homomorphism (verify), it's surjective because $f$ is, and it's injective because if something maps to the identity then it must be in the kernel of $f$ and so it must be the identity in the quotient ring.

Groups of low order, a table: