Basic theorems

Note: The theorem and page numbers refer to the text book, An Introduction to Mathematical Thinking: Algebra and Number Systems, by Gilbert and Vanstone. The theorems listed here are the most basic and important ones in the course. In your exam, you may be asked to write proofs for these statements, or others that are in the syllabus.

• GCDs: Proposition 2.21 (basis for Euclidean Algorithm), Theorem 2.24 and its converse at the bottom of page number 30 (GCD characterization theorem).

• Prime numbers: Unique factorization theorem (2.54), Theorem 2.57 (GCDs in terms of prime factorization).

• Congruences: Proposition 3.14 (relation to remainders), Fermat's little theorem 3.42.

• RSA: Theorem 7.41 (correctness of RSA decoding).

• Complex numbers: Proposition 8.44(iv) (triangle inequality), De Moivre's Theorem 8.61.

• Polynomials: Remainder Theorem 9.12, Factor Theorem 9.14, Theorem 9.17 (number of roots of a polynomial).