# HTSEFP: Final

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

## 1Basic algebra¶

### 1.1Proof by induction¶

Prove something by induction.

#### 1.1.1General solution¶

Do you even induct?

### 1.2Power sets¶

Prove something involving power sets.

#### 1.2.1General 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.3Cardano's formula¶

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

#### 1.3.1General solution¶

Please let this not be on the final

#### 1.3.2Examples¶

• Assignment 1, question 1

### 1.4Set theory¶

Given some statement about sets. Is it true?

#### 1.4.1General solution¶

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

### 1.5Computing the gcd of integers¶

Given two (typically large) integers, compute their gcd

#### 1.5.1General 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.6Computing the gcd of polynomials¶

Given two polynomials, compute their gcd.

#### 1.6.1General 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.7Polynomial division¶

Divide two polynomials

#### 1.7.1General solution¶

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

#### 1.7.2Examples¶

• Assignment 3, questions 1 and 2

### 1.8Complex integers¶

Show that a complex number is an integer.

#### 1.8.1General 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.9Euclid's lemma¶

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

#### 1.9.1General 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.10Bézout's identity¶

State and prove it.

#### 1.10.1General 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.11The fundamental theorem of arithmetic¶

State and prove it.

#### 1.11.1General solution¶

Unique factorisation into primes with powers.

Uniqueness proof: induction.

### 1.12Infinitely many primes¶

Prove that there are infinitely many primes.

## 2Solving congruences¶

### 2.1Calculate an exponent mod n¶

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

#### 2.1.1General 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.2Congruence equations¶

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

Trial and error

### 2.3Number 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.1General 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.4Proving Fermat's Little Theorem¶

State and prove Fermat's Little Theorem.

#### 2.4.1General 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.5Modular proofs¶

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

#### 2.5.1General 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.2Examples¶

• Assignment 2, question 11
• Assignment 2, question 5

### 2.6Invertible 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.1General 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.2Examples¶

• Assignment 2, question 8
• Assignment 2, question 6

## 3Rings and ideals¶

### 3.1Identifying ideals¶

Is this an ideal????

#### 3.1.1General solution¶

Properties:

2. Closed under ring multiplication

#### 3.1.2Examples¶

• Assignment 4, questions 6-10

### 3.2Subrings¶

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

#### 3.2.1General solution¶

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

1. The identity element is in $S$
3. Closed under multiplication

#### 3.2.2Examples¶

• Assignment 4, question 2

### 3.3Describing 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.1General solution¶

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

### 3.4Proving 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.1General 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.5Maximal and prime ideals¶

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

#### 3.5.1General 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.6Finding the unique ideals¶

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

Write them out.

### 3.7Finding inverses¶

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

#### 3.7.1General 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.8Is it a field?¶

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

#### 3.8.1General 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.9Using the first isomorphism theorem¶

Make use of the first isomorphism theorem in some way.

idk

### 3.10Proving irreducibility or primality¶

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

#### 3.10.1General 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.11Proving two rings are homomorphic¶

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

#### 3.11.1General solution¶

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

#### 3.11.2Examples¶

• Assignment 3, question 3
• Assignment 4, question 3
• Assignment 4, question 12

### 3.12Proving two rings are not isomorphic¶

Given two rings, prove that they are not isomorphic.

#### 3.12.1General solution¶

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

### 3.13Proving principality¶

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

#### 3.13.1General 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.2Examples¶

• Assignment 4, question 11 (the first part)

### 3.14Proving non-principality¶

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

### 3.15Constructing finite fields¶

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

#### 3.15.1General 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.16Identifying the units of a ring¶

Here is a ring. What are its units?

#### 3.16.1General 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$.

## 4Group theory¶

### 4.1Orders of elements in permutation groups¶

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

#### 4.1.1General solution¶

Factors, or lcm of factors

### 4.2Isomorphisms between groups of n elements¶

Are any two groups of $n$ elements isomorphic?

#### 4.2.1General solution¶

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

### 4.3The first isomorphism theorem for groups¶

State and/or prove it.

Same as rings

### 4.4Relations on groups¶

Here's a relation. What are its properties?

#### 4.4.1General 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.5The 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.1General solution¶

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

### 4.6Proving Lagrange's theorem¶

State and prove Lagrange's theorem.

#### 4.6.1General 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.7Number 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.1General solution¶

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

### 4.8Finding the order of a group¶

Find the order (cardinality) of a group.

Depends I guess

### 4.9Proving isomorphism between groups¶

Given two groups, prove that they are isomorphic.

#### 4.9.1General solution¶

Create a group homomorphism. Show that it is bijective.

### 4.10Normal subgroups¶

Prove that something is a normal subgroup.

#### 4.10.1General solution¶

Create a homomorphism.

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

depends

### 4.12Properties involving orders¶

Prove or disprove something involving orders.

#### 4.12.1General 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.13Proving the lack of surjective homomorphisms¶

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

### 4.14Permutation group elements¶

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

#### 4.14.1General 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.