**Maintainer:**admin

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

*1*Proving a theorem¶

Prove some theorem we saw in class.

*1.1*General solution¶

Depends on the theorem. See the review notes

*1.2*Examples¶

- 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)

*2*Other proofs¶

Prove something that is not a theorem seen in class.

*2.1*General solution.¶

See the list of proof techniques

*2.2*Examples¶

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

*3*Cardano's formula¶

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

*3.1*General solution¶

idk

*3.2*Examples¶

- Assignment 1, question 1

*4*Invertible elements¶

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

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

*4.2*Examples¶

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

*5*Modular arithmetic¶

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

*5.1*General 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.2*Examples¶

*6*Modular proofs¶

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

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

*6.2*Examples¶

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

*7*Congruence relations¶

Solve a congruence relation.

*7.1*General solution¶

Trial and error

*7.2*Examples¶

*8*Complex integers¶

Show that a complex number is an integer.

*8.1*General 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.2*Examples¶

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

*9*Computing the gcd of integers¶

Given two (typically large) integers, compute their gcd

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

*9.2*Examples¶

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

*10*Computing the gcd of polynomials¶

Given two polynomials, compute their gcd.

*10.1*General solution¶

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

*10.2*Examples¶

N/A

*11*Polynomial division¶

Divide two polynomials

*11.1*General solution¶

Just use polynomial long division

*11.2*Examples¶

- Assignment 3, some questions I forget which