CS 173: Skills list for Examlet 8
- Divisibility
- Quote back definitions, and decide if simple statements involving them are true
- For example, special cases for divides: zero is even, zero divides itself but not any other integer, and every integer divides zero; division for negatives.
- Understand the corresponding shorthand notation: a is a factor of b, b is a multiple of a
- Prove number theory claims involving the divisibility
- State and use the Division theorem:
- Compute quotient and remainder of a pair of numbers.
- Prove properties of quotients and remainders, and use the Division theorem to prove facts about numbers.
- (Co)primality and GCDs
- Know what a prime number is, and that every integer greater than 1 can be written as a unique weakly decreasing sequence of primes
- Define gcd(a,b), and decide if statements involving gcd are true.
- Know what it means for two numbers to be relatively prime, i.e., gcd(a,b) = 1.
- Compute the gcd of two (not necessarily positive) numbers, say, using the Euclidean algorithm, i.e. trace the execution of the algorithm.
- Prove simple facts about gcd.
- Know Bézout's theorem that states that there exist integers s,t so that gcd(a,b) = as+bt, and use Bézout's theorem to prove facts about numbers.
- Congruence modulo n
- Understand notation for when a and b are congruent modulo n, as well as congruence classes
- Know that congruence modulo n is an equivalence relation
- Do arithmetic on congruence classes, especially using remainders to simplify calculations
- Prove simple theorems about congruence modulo n.