Pigeon-hole principle (box principle), induction, elementary properties of divisibility, elementary combinatorics (permutations and combinations, binomial coefficients), elementary reasoning with graphs, elementary probability theory