**Maintainer:**admin

A guide to solving the various types of problems encountered in this course.

- 1 Basic algebra
- 1.1 Proof by induction
- 1.2 Power sets
- 1.3 Cardano's formula
- 1.4 Set theory
- 1.5 Computing the gcd of integers
- 1.6 Computing the gcd of polynomials
- 1.7 Polynomial division
- 1.8 Complex integers
- 1.9 Euclid's lemma
- 1.10 Bézout's identity
- 1.11 The fundamental theorem of arithmetic
- 1.12 Infinitely many primes

- 2 Solving congruences
- 3 Rings and ideals
- 3.1 Identifying ideals
- 3.2 Subrings
- 3.3 Describing quotient rings
- 3.4 Proving the Chinese Remainder Theorem
- 3.5 Maximal and prime ideals
- 3.6 Finding the unique ideals
- 3.7 Finding inverses
- 3.8 Is it a field?
- 3.9 Using the first isomorphism theorem
- 3.10 Proving irreducibility or primality
- 3.11 Proving two rings are homomorphic
- 3.12 Proving two rings are not isomorphic
- 3.13 Proving principality
- 3.14 Proving non-principality
- 3.15 Constructing finite fields
- 3.16 Identifying the units of a ring

- 4 Group theory
- 4.1 Orders of elements in permutation groups
- 4.2 Isomorphisms between groups of n elements
- 4.3 The first isomorphism theorem for groups
- 4.4 Relations on groups
- 4.5 The zero group homomorphism
- 4.6 Proving Lagrange's theorem
- 4.7 Number of elements of a given order
- 4.8 Finding the order of a group
- 4.9 Proving isomorphism between groups
- 4.10 Normal subgroups
- 4.11 Properties of simple groups
- 4.12 Properties involving orders
- 4.13 Proving the lack of surjective homomorphisms
- 4.14 Permutation group elements

*1*Basic algebra¶

*1.1*Proof by induction¶

Prove something by induction.

*1.1.1*General solution¶

Do you even induct?

*1.1.2*Examples¶

- Fall 2005 final, question 1
- Assignment 1, question 5
- Assignment 1, question 7
- Assignment 1, question 8

*1.2*Power sets¶

Prove something involving power sets.

*1.2.1*General solution¶

For example, that there is no bijection between a set and its power set. Use a proof by contradiction, and consider the set of all elements that are mapped to a set they are not in, and think about what a hypothetical bijection would do to this function.

*1.2.2*Examples¶

- Sample midterm, question 1
- Assignment 1, question 9

*1.3*Cardano's formula¶

Use Cardano's formula to find the roots for some cubic equation.

*1.3.1*General solution¶

Please let this not be on the final

*1.3.2*Examples¶

- Assignment 1, question 1

*1.4*Set theory¶

Given some statement about sets. Is it true?

*1.4.1*General solution¶

Draw the Venn diagram? If you can't do that, think about it using examples.

*1.4.2*Examples¶

*1.5*Computing the gcd of integers¶

Given two (typically large) integers, compute their gcd

*1.5.1*General solution¶

Use the Euclidean algorithm. It's pretty easy.

To confirm, divide each number by its proposed gcd. If it works, it's definitely a common divisor (although it may not be the *greatest* if you made a mistake somewhere). If it doesn't divide evenly, then you definitely made a mistake somewhere.

*1.5.2*Examples¶

- Sample midterm, question 2
- Assignment 1, question 6

*1.6*Computing the gcd of polynomials¶

Given two polynomials, compute their gcd.

*1.6.1*General solution¶

Same as the previous one, except with polynomial division. Shouldn't be too hard.

This often occurs in $\mathbb Z/n\mathbb Z$, so keep that in mind.

If we have to do this in general (with variables as opposed to concrete numbers), it's a bit harder, but not impossible; just run through the Euclidean algorithm and see what happens.

*1.6.2*Examples¶

- Fall 2006, question 2 (part A), Fall 2007, question 2 (part A), Fall 2009, question 3 (part A)
- Practice final, question 3
- Assignment 3, question 4

*1.7*Polynomial division¶

Divide two polynomials

*1.7.1*General solution¶

Just use polynomial long division. (There's a package for it.)

*1.7.2*Examples¶

- Assignment 3, questions 1 and 2

*1.8*Complex integers¶

Show that a complex number is an integer.

*1.8.1*General solution¶

First, find the polar representation of the complex number (draw the triangle, calculate $r$ and $\theta$). Then, use Euler's identity: $e^{i\theta} = \cos(\theta) + i\sin(\theta)$ (twice if necessary). You'll get sin(x) where x comes out to a multiple of pi and so the complex coefficient will be 0.

*1.8.2*Examples¶

- Assignment 1, question 4
- Fall 2012 midterm, question 1

*1.9*Euclid's lemma¶

State and prove it using only the basic properties of the gcd.

*1.9.1*General solution¶

If $p$ is prime, and $p \mid ab$, then $p \mid a$ or $p \mid b$.

Assume $\gcd(p, a) = 1$. Then there exist $u, v$ such that $up + av = 1$. Multiply both sides by $b$ and we get $bup + bav = b$. Now, $p \mid bup$, and $p \mid ab$ so $p \mid bav$. Then $p \mid b$.

*1.9.2*Examples¶

*1.10*Bézout's identity¶

State and prove it.

*1.10.1*General solution¶

There exist $u, v$ such that $ua + vb = \gcd(a, b)$.

Proof: let $S$ be the set of all positive integers that can be expressed in the form $ua + vb$. This is not empty, for $a^2+b^2$ is in the set. Let $d$ be the minimum element. We can write $a = qd + r = (ua + vb)q + r = qua + qvb + r$. So $r = a - qua + qvb = (1-qu)a + (qv)b$. So $r$ is a linear combo of $a$ and $b$. But $r$ can't be in $S$ as that would contradict the minimality of $d$. So $r = 0$. So then $a = qd$ so $d \mid a$. Same for $b$.

To prove that it's the greater divisor, just note that any other divisor must also divide $d$, etc.

*1.10.2*Examples¶

*1.11*The fundamental theorem of arithmetic¶

State and prove it.

*1.11.1*General solution¶

Unique factorisation into primes with powers.

Existence proof: contradiction, minimality.

Uniqueness proof: induction.

*1.11.2*Examples¶

- Fall 2006 final, question 5 (b) (part B) (just the existence part)

*1.12*Infinitely many primes¶

Prove that there are infinitely many primes.

*1.12.1*General solution¶

Euclid's proof, by contradiction.

*1.12.2*Examples¶

*2*Solving congruences¶

*2.1*Calculate an exponent mod n¶

Calculate $a^b \pmod c$ where $a$, $b$ and $c$ are given and $b$ is typically very large.

*2.1.1*General solution¶

If $b$ is composite: First, break down $a$ into its prime divisors. Then, use the Chinese remainder theorem, and solve for $a$ (see below).

If $b$ is prime: Fermat's little theorem is very useful. Divisibility tests can also come in handy.

**Remark**: this kind of question is ubiquitous (it shows up once in pretty much every past exam). Make sure you know how to do questions of this type without having to spend too much time trying to remember what the correct procedure is.

*2.1.2*Examples¶

- Sample midterm, question 3
- Fall 2012 midterm, question 3
- Fall 2006 final, question 6 (part A)
- Fall 2007 final, question 4 (part A)
- Fall 2009 final, question 9 (part I)
- Practice final, question 1

*2.2*Congruence equations¶

Solve a congruence equation. It may or may not be linear.

*2.2.1*General solution¶

Trial and error

*2.2.2*Examples¶

- Fall 2005 final, question 2
- Fall 2007 final, question 2 (b) (part II)
- Fall 2009 final, question 2 (b) (part II)
- Fall 2012 midterm, question 4
- Assignment 2, question 4

*2.3*Number of solutions to a congruence equation¶

How many solutions does $x^a = b$ have in $\mathbb Z / n \mathbb Z$ (with $a, b, n$ given)?

*2.3.1*General solution¶

It seems that it has something to do with the prime decomposition of $n$. If $n = pq$ where $p, q$ are prime, then the answer is $\leq a^2$. Think about it. Chinese Remainder Theorem!!

*2.3.2*Examples¶

*2.4*Proving Fermat's Little Theorem¶

State and prove Fermat's Little Theorem.

*2.4.1*General solution¶

Proof: prove that a prime divides its binomial coefficient, then, induction.

You may also be asked to prove this using Lagrange's theorem from group theory. The unit group for $\mathbb Z/p\mathbb Z$ has $p-1$ elements, so its order is that, and the order of any element divides that. If $k$ is the order of $a$ then $a^k = 1$, and $a^{p-1} = a^{mk} = (a^m)^k = 1^k = 1$.

*2.4.2*Examples¶

- Practice final, question 5 (requires using Lagrange's theorem)
- Fall 2005 final, question 3
- Assignment 2, question 9 (the binomial coefficient part)
- Assignment 2, question 10 (the rest of it)
- Assignment 5, question 9 (using Lagrange's theorem)

*2.5*Modular proofs¶

Show that $a^x \equiv a \pmod y$ for all $a$, where $x$ and $y$ are given.

*2.5.1*General solution¶

Break $a$ down into its prime divisors if it's not prime (if it is, this trivially uses FLT and so is unlikely to be asked). Then, use the Chinese remainder theorem, and FLT on each part.

*2.5.2*Examples¶

- Assignment 2, question 11
- Assignment 2, question 5

*2.6*Invertible elements and primitive roots¶

Find all the invertible elements in $\mathbb{Z}/n\mathbb{Z}$ where $n$ is given. Also, find the primitive roots.

*2.6.1*General solution¶

List all the elements that are relatively prime to $n$. If $n$ is simply prime, then all the elements in the ring (which is in fact a field) are invertible.

Finding primitive roots: try every number (start from 2). Note that for non-prime $n$, there are no primitive roots.

*2.6.2*Examples¶

- Assignment 2, question 8
- Assignment 2, question 6

*3*Rings and ideals¶

*3.1*Identifying ideals¶

Is this an ideal????

*3.1.1*General solution¶

Properties:

- Closed under addition
- Closed under ring multiplication

*3.1.2*Examples¶

- Assignment 4, questions 6-10

*3.2*Subrings¶

Given a subset $S$ of a ring, is it a subring?

*3.2.1*General solution¶

For $S$ to be a subring, it must satisfy the following conditions:

- The identity element is in $S$
- Closed under addition
- Closed under multiplication

*3.2.2*Examples¶

- Assignment 4, question 2

*3.3*Describing quotient rings¶

Give an example of a ring $R$ and an ideal $I$ in it which is not principal, and describe $R/I$.

*3.3.1*General solution¶

$(2, x)$ in $\mathbb Z[x]$. Isomorphic to $\mathbb Z/2\mathbb Z$

*3.3.2*Examples¶

- Practice final, question 2
- Practice final, question 6 (the last part of the question asks to describe a quotient ring)
- Assignment 4, question 11 (the last part, the non-principal example)

*3.4*Proving the Chinese Remainder Theorem¶

Prove the Chinese Remainder Theorem (that $\mathbb Z /(mn) \mathbb Z \cong \mathbb Z / m\mathbb Z \times \mathbb Z / n \mathbb Z$). Optionally: state the analogous theorem for the ring of polynomials with coefficients in a field.

*3.4.1*General solution¶

Create the following isomorphism: $f: a \mapsto a \pmod m, a \pmod n$. Show that it's a ring homo, injective (easy). Surjective: Bezout's identity, multiplying $um + vn = 1$ by $a$.

*3.4.2*Examples¶

- Fall 2006 final, question 3 (a) (part B), Fall 2007 final, question 2 (a) (part B), Fall 2009 final, question 2 (a) (part II) (the Chinese Remainder Theorem proof)
- Fall 2006 final, question 3 (b) (part B) (the ring of polynomials part only)

*3.5*Maximal and prime ideals¶

Define maximal and prime ideals. Prove something related to them.

*3.5.1*General solution¶

Maximal ideal: any ideal containing this ideal would have to be the whole ring.

Prime ideal: if $ab \in I$, then $a \in I$ or $b \in I$.

*3.5.2*Examples¶

*3.6*Finding the unique ideals¶

Given a list of ideals, how many unique ideals are there?

*3.6.1*General solution¶

Write them out.

*3.6.2*Examples¶

*3.7*Finding inverses¶

Find the inverse of an element in a (possibly quotient) ring.

*3.7.1*General solution¶

If it's a polynomial ring, and you're instructed to evaluate the element to several powers, then you'll probably find the inverse in there.

*3.7.2*Examples¶

*3.8*Is it a field?¶

Is this (likely quotient) ring a field? Prove it. Optionally: find a square root of something in it.

*3.8.1*General solution¶

If it's a quotient ring, then it depends on what you're modding by. If it's irreducible (for polynomials) or prime (for the integers), then it's a field. Otherwise, it's probably not.

If you have to prove it, use Bezout's identity to show that every element has an inverse (because the gcd is 1, etc). Also note that the irreducible polynomial that you're modding by has a root in this quotient ring (because $f(x) = 0$).

Note that $\mathbb Z$ is not a field. $\mathbb Q$ is.

*3.8.2*Examples¶

- Fall 2006, question 4 (part A)
- Fall 2006, question 4 (part B)
- Fall 2007, question 3 (a) (part B)
- Fall 2007, question 3 (c) (part B) (finding the square root of 2)

*3.9*Using the first isomorphism theorem¶

Make use of the first isomorphism theorem in some way.

*3.9.1*General solution¶

idk

*3.9.2*Examples¶

- Fall 2007, question 3 (d)-(e) (part B)
- Assignment 5, question 1

*3.10*Proving irreducibility or primality¶

Given a polynomial ring or a square root ring or something, show that an element is irreducible or prime.

*3.10.1*General solution¶

For the $\sqrt{-z}$ where $z$ is some integer ring, make use of the norm function, $f: a + b \sqrt{-z} \mapsto a^2 + zb^2$. Use the fact that this function is multiplicative and check each of the factors, etc.

*3.10.2*Examples¶

- Practice final, question 6 (just the first part)
- Fall 2007, question 3 (b) (part B)
- Assignment 2, question 1

*3.11*Proving two rings are homomorphic¶

Given two rings, create a ring homomorphism between them. Possibly an isomorphism.

*3.11.1*General solution¶

Create a function, show that it's closed under addition and multiplications

*3.11.2*Examples¶

- Assignment 3, question 3
- Assignment 4, question 3
- Assignment 4, question 12

*3.12*Proving two rings are not isomorphic¶

Given two rings, prove that they are not isomorphic.

*3.12.1*General solution¶

If they have different cardinalities, you can prove that there is no bijection between them. TODO

*3.12.2*Examples¶

*3.13*Proving principality¶

Show that some ring is a principal ideal domain (all ideals are principal).

*3.13.1*General solution¶

Assume that the ideal is not the trivial ideal (if it were, it would be, well, trivial). Then we can use Euclidean division and the well-ordering principle?

*3.13.2*Examples¶

- Assignment 4, question 11 (the first part)

*3.14*Proving non-principality¶

Show that the ideal generated by certain elements is not principal.

*3.14.1*General solution¶

Norm function, or just, contradiction

*3.14.2*Examples¶

- Practice final, question 6 (the second part)

*3.15*Constructing finite fields¶

Construct a field consisting of $p^n$ elements where $p$ is prime and $n \geq 1$.

*3.15.1*General solution¶

If $n = 1$, then $\mathbb Z / p \mathbb Z$ will do the trick, and we can use this field for the other part. Otherwise, find an irreducible polynomial of degree $n$. To find one, write out the numbers in the field to the power of $n$. You'll probably find that there is at least one number that never occurs. Let's call it $t$. So then you know that $a^n = t$ has no solutions for $a \in \mathbb Z / p \mathbb Z$, meaning that $x^n - t$ should be irreducible.

*3.15.2*Examples¶

*3.16*Identifying the units of a ring¶

Here is a ring. What are its units?

*3.16.1*General solution¶

Identify the things that have multiplicative inverses in the ring. For $\mathbb Z /n \mathbb Z$, it's the numbers that are relatively prime to $n$. For $\mathbb Z$, it's 1 and -1. For the ring of dual numbers, it's $a + b \epsilon$ where $a \neq 0$.

*3.16.2*Examples¶

- Fall 2007 final, question 9 (part A)
- Assignment 2, question 8

*4*Group theory¶

*4.1*Orders of elements in permutation groups¶

You're given a permutation group, $S_n$. What orders can its elements have?

*4.1.1*General solution¶

Factors, or lcm of factors

*4.1.2*Examples¶

*4.2*Isomorphisms between groups of n elements¶

Are any two groups of $n$ elements isomorphic?

*4.2.1*General solution¶

If $n$ is prime, yes. Otherwise, not necessarily.

*4.2.2*Examples¶

*4.3*The first isomorphism theorem for groups¶

State and/or prove it.

*4.3.1*General solution¶

Same as rings

*4.3.2*Examples¶

*4.4*Relations on groups¶

Here's a relation. What are its properties?

*4.4.1*General solution¶

I'm not sure if this is in the syllabus this semester, but you can basically just check each property to see if it holds.

Note that the conjugacy relation is an equivalence relation. So is the relation for making cosets. TODO: write the formula for them

*4.4.2*Examples¶

*4.5*The zero group homomorphism¶

Every homomorphism of groups from $\mathbb Z / n\mathbb Z \to \mathbb Z$ is the zero homomorphism. True or false?

*4.5.1*General solution¶

Yep. See the first link in the examples for the reasoning.

*4.5.2*Examples¶

*4.6*Proving Lagrange's theorem¶

State and prove Lagrange's theorem.

*4.6.1*General solution¶

The theorem: let $G$ be a finite group and let $H$ be a subgroup of $G$. Then, the order of $H$ divides the order of $G$.

Proof: show that subgroups have the same cardinality (isomorphism)

*4.6.2*Examples¶

- Fall 2009 final, question 3 (part II)
- Practice final, question 5 (only stating Lagrange's theorem)

*4.7*Number of elements of a given order¶

Show that a group has at most $t$ elements of order $t$ for all $t \geq 1$.

*4.7.1*General solution¶

Polynomials have at most $t$ roots, use FLT.

*4.7.2*Examples¶

*4.8*Finding the order of a group¶

Find the order (cardinality) of a group.

*4.8.1*General solution¶

Depends I guess

*4.8.2*Examples¶

- Practice final, question 7 (the first part)

*4.9*Proving isomorphism between groups¶

Given two groups, prove that they are isomorphic.

*4.9.1*General solution¶

Create a group homomorphism. Show that it is bijective.

*4.9.2*Examples¶

- Practice final, question 7 (the second part)

*4.10*Normal subgroups¶

Prove that something is a normal subgroup.

*4.10.1*General solution¶

Create a homomorphism.

Or, show that the left and right cosets are equal.

*4.10.2*Examples¶

*4.11*Properties of simple groups¶

Prove something about simple groups.

*4.11.1*General solution¶

depends

*4.11.2*Examples¶

*4.12*Properties involving orders¶

Prove or disprove something involving orders.

*4.12.1*General solution¶

Remember what order means: the order of an element $a \in G$ is the least positive integer $t$ such that $a^t = e$.

*4.12.2*Examples¶

*4.13*Proving the lack of surjective homomorphisms¶

Prove that there does not exist a surjective homomorphism between two groups.

*4.13.1*General solution¶

Proof by contradiction. TODO

*4.13.2*Examples¶

*4.14*Permutation group elements¶

List the conjugacy classes and normal subgroups in $S_n$.

*4.14.1*General solution¶

Things with the same-length cycle decomposition are in the same conjugacy class.

The normal subgroups are: the trivial subgroup, the whole group, and the disjoint union of the conjugacy classes whose elements are composed of an even number of even cycles.

*4.14.2*Examples¶

- Fall 2005 final, question 8
- Assignment 5, question 12