Home MATH 235 HTSEFP: Final

HTSEFP: Final CC-BY-NC

Maintainer: admin

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

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

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

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

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

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

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

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

1.11The fundamental theorem of arithmetic

State and prove it.

1.11.1General solution

Unique factorisation into primes with powers.

Existence proof: contradiction, minimality.

Uniqueness proof: induction.

1.11.2Examples

1.12Infinitely many primes

Prove that there are infinitely many primes.

1.12.1General solution

Euclid's proof, by contradiction.

1.12.2Examples

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

2.2Congruence equations

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

2.2.1General solution

Trial and error

2.2.2Examples

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

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

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:

  1. Closed under addition
  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$
  2. Closed under addition
  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.3.2Examples

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

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

3.6Finding the unique ideals

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

3.6.1General solution

Write them out.

3.6.2Examples

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

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

3.9Using the first isomorphism theorem

Make use of the first isomorphism theorem in some way.

3.9.1General solution

idk

3.9.2Examples

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

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

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.14.1General solution

Norm function, or just, contradiction

3.14.2Examples

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

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

3.16.2Examples

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

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

4.3The first isomorphism theorem for groups

State and/or prove it.

4.3.1General solution

Same as rings

4.3.2Examples

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

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

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

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

4.8Finding the order of a group

Find the order (cardinality) of a group.

4.8.1General solution

Depends I guess

4.8.2Examples

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

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.

4.10.2Examples

4.11Properties of simple groups

Prove something about simple groups.

4.11.1General solution

depends

4.11.2Examples

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

4.13Proving the lack of surjective homomorphisms

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

4.13.1General solution

Proof by contradiction. TODO

4.13.2Examples

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.

4.14.2Examples