|
Course Topics
| CHAPTER 1 Number Theory |
- 1.1 The division algorithm and greatest common divisors
- divisibility of integers, greatest common divisor and least common multiple, Eulcidean algorithm, relatively prime
- 1.2 Mathematical Induction
- principle of mathematical induction, base case, inductive step, inductive hypothesis, strong induction
- 1.3 Primes and the Unique Factorization Theorem
- prime numbers, sieve of Eratosthenes, Fundamental Theorem of Arithmetic
- 1.4 Congruence classes
- a congruent to b modulo n, congruence classes, the algebra of congruence classes, invertible, zero-divisors
- 1.5 Solving linear congruences
- linear congruences
- 1.6 Euler's Theorem and public key codes
- order modulo n, Fermat's Theorem, Euler's phi-function, Euler's Theorem, public key codes
|
| CHAPTER 2 Sets, functions and relations |
- 2.1 Elementary set theory
- element of a set, equality of sets, empty set, subset, proper subsets, Venn diagrams, universal set, complement, relative complement, union, intersection, disjoint, the algebra of sets, Cartesian product
- 2.2 Functions
- function/map, domain, codomain, image, surjection (onto), injection (one-to-one), bijection, permutation, composition of functions, inverse, cardinality of sets
- 2.3 Relations
- relation, reflexive, symmetric, transitive, equivalence relation, equivalence classes
|
| CHAPTER 3 Logic and mathematical argument |
- 3.1 Propositional logic
- proposition, negation, and, or (inclusive/exclusive), truth table, implication, converse, contrapositive, tautology, contradiction, logical equivalence, logical identities (commutativity, associativity, distributivity, De Morgan laws, etc.)
- 3.2 Quantifiers
- universal and existential quantifiers, negation of quantified statements
- 3.3 Some proof strategies
- examples and counterexamples, direct proof, proof by contradiction, proof by cases, proof by contrapositive, showing equality of sets, induction
|
| CHAPTER 4 Examples of groups |
- 4.1 Permutations
- permutation, symmetric group, transposition, cycle, disjoint cycles, two-line notation, cycle notation, cycle decomposition
- 4.2 The order and sign of a permutation
- the order of a permutation, the sign of a permutation, even/odd permutations
- 4.3 Definition and examples of groups
- group, binary operator, closure, identity, inverse, associativity, commutative/Abelian, alternating group, general linear group, dihedral group
- 4.4 Algebraic structures
- semigroup, ring, field, zero-divisor, integral domain, vector space,
|
| CHAPTER 5 Group theory and error-correcting codes |
- 5.1 Preliminaries
- order of a group element, subgroup, cyclic group,
- 5.2 Cosets and Lagrange's Theorem
- left/right cosets, the order of a group, Lagrange's Theorem
- 5.3 Groups of small order
- 5.4 Error-detecting and error-correcting codes
|
|