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

2Other proofs¶

Prove something that is not a theorem seen in class.

2.1General solution.¶

See the list of proof techniques

3Cardano's formula¶

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

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.

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.

Trial and error

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.

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.

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.

N/A

11Polynomial division¶

Divide two polynomials

11.1General solution¶

Just use polynomial long division

11.2Examples¶

• Assignment 3, some questions I forget which