IOQM key terms

A relation where one integer divides another with zero remainder. Written a | b, it means b = ak for some integer k. It underpins congruences, factorisation arguments, and most olympiad number theory.

Two integers are congruent mod n when their difference is a multiple of n. Congruences preserve addition and multiplication, letting you replace large numbers by small remainders and reason about last digits or divisibility.

The largest positive integer dividing both of two given integers. It can always be written as an integer combination of them, a fact that drives Bezout-style arguments and coprimality proofs.

The smallest positive integer divisible by each of two given integers. For positive a and b it equals ab divided by their greatest common divisor, a relation frequently used when counting multiples in a range.

A repeated division-with-remainder procedure that computes the greatest common divisor of two integers. Because remainders strictly decrease, the process terminates, and reversing the steps yields integer combinations.

An integer greater than one whose only positive divisors are one and itself. Primes are the multiplicative building blocks of the integers; questions often turn on their distribution, parity, or occurrence in expressions.

Every integer greater than one factors uniquely into primes, up to order. This uniqueness licenses comparing prime exponents on both sides of an equation, a standard tool in olympiad proofs.

The expression of a positive integer as a product of prime powers. The exponents reveal the number of divisors, the sum of divisors, and divisibility properties at a glance.

For a positive integer with prime factorisation into powers with exponents e1, e2, and so on, the number of positive divisors equals the product of each exponent plus one. It converts factorisation data into a count.

Two integers whose greatest common divisor is one. Coprimality often permits cancellation in congruences and, by Bezout's identity, guarantees an integer combination equal to one.

For a coprime to modulus n, the unique residue b with ab congruent to 1 mod n. It allows division in modular arithmetic and exists exactly when the two numbers are coprime.

If p is prime and a is not divisible by p, then a raised to p minus one is congruent to 1 modulo p. It simplifies large powers and tests primality-style claims.

The count of integers from 1 to n that are coprime to n. For a prime power it equals the power minus the previous power, and it is multiplicative across coprime factors.

A statement that simultaneous congruences with pairwise coprime moduli have a unique solution modulo the product of the moduli. It splits a hard problem into independent smaller ones.

An equation in several integer unknowns for which integer or positive integer solutions are sought. Techniques include factoring, bounding by size, parity, and modular obstruction.

An equation of the form ax + by = c in integers. Solutions exist exactly when the greatest common divisor of a and b divides c, and then they form an arithmetic family.

A proof technique that assumes a solution exists, constructs a strictly smaller one, and repeats, contradicting well-ordering of the positive integers. It is classic for showing no nonzero solutions exist.

If more objects than boxes are distributed, some box holds at least two. Generalised forms count forced multiplicities; the art lies in choosing boxes cleverly.

Counting a set by subtracting the number of objects failing a condition from the total. It simplifies problems where the direct count involves many overlapping cases.

A formula for the size of a union of sets that alternately adds and subtracts intersections. It corrects for double counting when events overlap.

An arrangement of objects in a definite order. The number of orderings of n distinct objects is n factorial; partial arrangements use falling factorials.

A selection of objects where order does not matter. The count of k-subsets of an n-element set is written as a binomial coefficient and computed by a ratio of factorials.

The number of ways to choose k objects from n, denoted by n above k. It appears in expansions, lattice-path counts, and identities such as symmetry and the hockey-stick rule.

The relation that a binomial coefficient equals the sum of the two coefficients above it in Pascal's triangle. It underlies induction proofs of combinatorial identities.

A formula expanding a sum of two terms raised to a power as a sum of terms, each a binomial coefficient times powers of the parts. It links algebra with counting.

A method that selects the largest, smallest, or otherwise extreme object in a configuration and exploits the constraints that extremality imposes. It is powerful in combinatorics and geometry.

A quantity unchanged by every allowed operation. If a target state has a different value of the invariant, it is unreachable; this settles many impossibility puzzles.

A quantity that always moves in one direction under the allowed operations, such as a sum that strictly decreases. Because it cannot decrease forever, the process must stop.

Whether an integer is even or odd. Parity arguments reduce problems to two cases and quickly rule out configurations or solutions that would require a mismatch.

A collection of vertices with edges joining some pairs. Graphs model relations and networks; questions concern paths, cycles, degrees, and colourings.

The number of edges incident to a vertex in a graph. Degree sums control the existence of paths, and degree sequences constrain possible graphs.

In any graph the sum of all vertex degrees equals twice the number of edges. A consequence is that the number of odd-degree vertices is even.

A connected graph with no cycles. A tree on n vertices has exactly n minus one edges, and any two vertices are joined by a unique simple path.

In any triangle, each side is shorter than the sum of the other two, and longer than their difference. It gives bounds and equality conditions used in optimisation geometry.

In a right triangle, the square on the hypotenuse equals the sum of the squares on the legs. Its converse identifies right angles and it converts lengths into algebraic relations.

Triangles with equal corresponding angles, whose corresponding sides are proportional. Similarity transfers length ratios and is a primary tool for computing unknown lengths.

For a point and a circle, the product of distances to the circle along any secant through the point. It is constant and equals the squared tangent length when the point is outside.

A quadrilateral whose vertices lie on one circle. Opposite angles are supplementary, and intersecting chords or secants yield equal products of segment lengths.

In a cyclic quadrilateral, the product of the diagonals equals the sum of the products of the two pairs of opposite sides. It converts cyclic geometry into length equations.

An angle bisector in a triangle divides the opposite side in the ratio of the adjacent sides. Its converse helps prove concurrency or locate points on a side.

A criterion for three cevians of a triangle to be concurrent: the product of three side ratios equals one. Menelaus' theorem gives the analogous collinearity condition.

For nonnegative reals, the arithmetic mean is at least the geometric mean, with equality only when all are equal. It bounds sums given products and proves many optimisation results.

For real sequences, the square of the sum of products is at most the product of the sums of squares. It bounds expressions and pins down equality cases.

The remainder when a polynomial is divided by x minus a equals the polynomial evaluated at a. Hence a is a root exactly when x minus a divides the polynomial.

A number a is a root of a polynomial exactly when x minus a is a factor. Repeated roots correspond to repeated factors, which constrains coefficients.

Relations expressing sums and products of polynomial roots through coefficients. For a quadratic, the root sum is minus b over a and the product is c over a.

A polynomial unchanged when its variables are permuted. Every such polynomial can be written using elementary symmetric sums, which are tied to Vieta's formulas.

An expression adding squared terms. Completing the square rewrites quadratics to expose extrema, and sums of squares are nonnegative, which yields inequalities.

An equation whose unknown is a function, required to hold for all admissible inputs. Standard moves are substituting special values, checking injectivity, and testing simple candidate functions.

Every nonempty set of positive integers has a least element. It justifies minimal-counterexample proofs and underpins induction and descent arguments.