Shows that divisibility is transitive: If a|b and b|c, a|c
If a|b and a|c, then a|(bx + cy)
The denominator must be smaller if divisible: If a|b and b≠0, then |a|≤|b|
There exists q and r s.t. b = aq + r, where 0 ≤ r < a
Bezout's Lemma (Extended Euclidean Algorithm)
For proofs, try contradictions, contra-positives or direct proofs. For induction, find a statement P(n) that is true or false. Show that P(1) is true. Assume P(k) is true. Show that P(k+1) is true.
GCD, LDE, Congruences, linear congruences, Simultaneous Congruences, FlT, CRT, SM, RSA, Complex Numbers, Fields
Congruences can add, subtract, multiply. To divide, apply CD. To simplify exponents, apply FlT.
For simultaneous congruences, use chinese remainder theorem.
For Linear congruences, apply knowledge of Linear Diophantine Equations.