Olympiad Number Theory | Divisibility, Modular Arithmetic and Diophantine Equations

Build number theory as a connected olympiad system

Olympiad number theory becomes manageable when divisibility, congruences, prime factorisation and Diophantine equations stop looking like separate chapters. They are different views of integer structure. Divisibility asks whether one integer contains another as an exact factor. The greatest common divisor measures shared factor structure. Modular arithmetic records what remains after division. Prime exponents measure how strongly factors occur. Diophantine equations ask which integer choices can satisfy an algebraic relationship. A competition problem often moves through several of these views before the decisive step appears.

Divisibility must support proof

The statement a divides b means that b=ak for some integer k. This definition is more useful than a divisibility test because it can be inserted into an argument. If a divides b and a divides c, every integer linear combination xb+yc is also divisible by a. That observation powers gcd arguments, Euclid’s algorithm and many impossibility proofs. Students should practise moving both ways: from divisibility notation to an equation, and from an equation back to a divisibility conclusion.

Use gcd as structure, not a calculator command

The identity gcd(a,b)=gcd(b,a−qb) explains why subtracting a multiple can simplify a divisibility problem without changing its common-divisor structure. Consecutive integers are coprime because any common divisor must also divide their difference, one. In olympiad work the useful question is often not “what is the gcd?” but “what else must every common divisor be forced to divide?”

Choose a modulus because it exposes the target structure

Congruence a≡b (mod n) means n divides a−b. Modulo 2 reveals parity; modulo 4 and 8 often control squares; modulo 3 or 9 interacts with digit sums. Random modular arithmetic creates noise. Instead ask what residue pattern would make the desired equation impossible. Squares modulo 4 are only 0 or 1, so an equation requiring a square to be 2 or 3 modulo 4 cannot hold. The modulus is a lens: choose one that compresses the expression while preserving the feature you need.

Prime exponents reveal perfect powers

A perfect square has even exponent at every prime; a perfect cube has exponents divisible by three. If a product is a square and two factors are coprime, each factor must itself be a square. This converts a global condition on a product into local conditions on coprime components. For a prime p, the valuation v_p(n) records the exponent of p in n, and v_p(ab)=v_p(a)+v_p(b). Even without advanced p-adic theory, this is a compact way to find the prime carrying the decisive imbalance.

Linear Diophantine equations begin with the gcd condition

The equation ax+by=c has integer solutions exactly when gcd(a,b) divides c. This follows from Bézout’s identity and the fact that every integer combination of a and b is divisible by their gcd. Once one solution is known, all solutions can be parameterised. Competition questions may hide this structure inside coin problems, lattice points, divisibility constraints or equations that first need rearrangement.

Nonlinear equations need reduction before search

For xy+x+y=n, adding one exposes (x+1)(y+1)=n+1. For equations involving squares, difference-of-squares factorisation may convert a nonlinear equation into a product with controlled parity. Other problems need modular restrictions or inequalities to bound variables. The general workflow is to reduce the infinite search space using structure before testing cases.

Worked example: reduce a divisor condition to a small remainder

Suppose n+1 divides n²+3. Modulo n+1, n≡−1, so n²+3≡4. Therefore n+1 must divide 4. An apparently infinite problem is reduced to the divisors of four. This is a characteristic olympiad move: replace a large expression by a small remainder under a divisor already present in the condition.

Common failure modes

Students often test examples and mistake a pattern for proof; divide a congruence by a non-invertible number; assume a product being a square makes each factor a square without checking coprimality; or search cases before establishing bounds. An error log should name the mathematical failure. “Illegal cancellation modulo 6” is actionable; “careless” is not.

Training and transfer

Build in layers: factors and gcd; elementary divisibility proofs; congruences and residue cycles; perfect powers and prime exponents; linear Diophantine equations; then mixed unfamiliar problems. A student owns the domain when they can generate useful questions without a chapter label: What divides what? What does the gcd force? Which modulus makes residues sparse? Can I factor the equation? Which prime exponent is decisive? Can I bound the variables?

Use the Mathematics Olympiad & Competition Hub for the wider route. When the problem moves into algorithms, finite fields, p-adic methods or advanced Diophantine computation, BTT’s Computational Number Theory series provides the deeper specialist continuation.