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