APMO · 4. Divisibility, primes and congruences
Divisibility proofs for APMO: extremal elements, congruences with size bounds, residues of squares, prime factorisation with the divisor sum, and binary arguments modulo 2^k − 1, with five fully proved APMO problems.
Use gcd rules and an extremal (largest/smallest) element to classify sets closed under a divisibility rule.
Reduce a divisibility modulo the divisor, bound the remainder and finish with residues of squares.
Bound the divisor sum σ(n)/n through the prime factorisation of n.
Work with binary expansions and the modulus 2^k − 1 in a minimal-counterexample proof.
Write complete proofs that cover every case and both directions of a "find all" answer.