Induction
- I can write the assumptions and conclusions of mathematical induction as a predicate logic inference
- I can apply mathematical induction to prove numerical identities and inequalities depending on a parameter
An example would be proving that
. Other examples are also present in the practice set. - I can recognize if a mathematical proof using induction applies it correctly See problems 4 and 8 and 11 in the practice set.
- I can apply complete induction, and understand an example of a proof using complete induction instead of usual induction. See the proof of existence of the fundamental theorem of arithmetic.
Divisibility, GCD and LCM; fundamental theorem of arithmetic
- I can check whether a number divides another number
- I can apply the basic properties of divisibility to numbers See Properties of divisibility
- I can compute the greatest common divisor of two (reasonable) numbers using the Euclidean algorithm See Euclid’s algorithm
- I understand the connection between the GCD and LCM of two numbers See this page.
- I can compute the
and of two numbers using prime factorization See Prime factorization method.
Division with remainder
- I can perform division with remainder for any reasonable numbers (for example, using long division)
- I understand the sequence of divisions with remainder leading to Euclid’s algorithm
- I understand the sequence of divisions with remainder leading to a number being expressed as a sum of powers of a base (rewriting a number in a given base)
Number systems and divisibility rules
- I can convert numbers between different bases
- I can perform arithmetic operations in different bases
- I can rewrite numbers in base
as a sum of powers of with coefficients in - I can prove various divisibility rules for numbers in different bases
Prime numbers and factorization
- I can factorize a (reasonably small) number in its prime factors
- I understand the meaning of unique factorization in the formulation of the fundamental theorem of arithmetic
- I can use prime factorization to determine if a number is a divisor of another number
Modular arithmetic, congruences
- I can perform arithmetic operations in modular arithmetic See Congruences
- I can rewrite the set of integers satisfying
as the set of integers . - I can determine if an element is invertible modulo
See Invertibility of elements in congruences - I can solve linear congruences of the form
where is invertible. - I can imply a congruence from an equality when solving a diophantine equation.
This sounds complicated, but this is just an explicit mention of the implication from
to for any . See Tricks in diophantine equations for some examples of problems.