HTSEFP: Midterm

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

1Proving a theorem¶

Prove some theorem we saw in class.

1.1General solution¶

Depends on the theorem. See the review notes

1.2Examples¶

• Fall 2005 final, question 3
• Sample midterm, question 4 (essentially Euclid's lemma)
• Fall 2009 final, question 2(a) (Chinese remainder theorem)
• Fall 2012 midterm, question 2 (Bézout's identity)

2Other proofs¶

Prove something that is not a theorem seen in class.

2.1General solution.¶

See the list of proof techniques

2.2Examples¶

• Sample midterm, question 1
• Assignment 2, question 7

3Cardano's formula¶

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

3.1General solution¶

idk

3.2Examples¶

• Assignment 1, question 1

4Invertible elements¶

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

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

4.2Examples¶

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

5Modular arithmetic¶

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

5.1General solution¶

First, break down $a$ into its prime divisors. Then, use the Chinese remainder theorem, and solve for $a$. Fermat's little theorem is very useful. Not too difficult usually.

5.2Examples¶

• Sample midterm, question 3
• Fall 2012 midterm, question 3

6Modular proofs¶

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

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

6.2Examples¶

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

7Congruence relations¶

Solve a congruence relation.

7.1General solution¶

Trial and error

7.2Examples¶

• Fall 2005 final, question 2
• Fall 2012 midterm, question 4

8Complex integers¶

Show that a complex number is an integer.

8.1General solution¶

First, find the polar representation of the complex number. Then, use Euler's identity (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.

8.2Examples¶

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

9Computing the gcd of integers¶

Given two (typically large) integers, compute their gcd

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

9.2Examples¶

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

10Computing the gcd of polynomials¶

Given two polynomials, compute their gcd.

10.1General solution¶

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

10.2Examples¶

N/A

11Polynomial division¶

Divide two polynomials

11.1General solution¶

Just use polynomial long division

11.2Examples¶

• Assignment 3, some questions I forget which