Maintainer: admin

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.

3.1General solution



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


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


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

7Congruence relations

Solve a congruence relation.

7.1General solution

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.



11Polynomial division

Divide two polynomials

11.1General solution

Just use polynomial long division


  • Assignment 3, some questions I forget which