IOQM flashcards

33 cards. Read the term and the definition here. The deck at the top of this page is optional.

Legendre's formula

The exponent of prime p in n! equals the sum of floor(n/p), floor(n/p^2), floor(n/p^3), and so on. Used to count trailing zeros and prime powers dividing factorials.

Euler's theorem

If gcd(a,m) equals 1, then a raised to phi(m) is congruent to 1 modulo m, where phi is Euler's totient function. Fermat's little theorem is the prime-modulus case.

Chinese remainder theorem

If moduli are pairwise coprime, a system of congruences has a unique solution modulo their product. Combine individual solutions to construct the answer.

gcd-lcm identity

For positive integers a and b, gcd(a,b) times lcm(a,b) equals a times b. This fails for three or more numbers, so use prime exponents there.

Linear Diophantine solvability

The equation ax+by=c has integer solutions exactly when gcd(a,b) divides c. One particular solution plus multiples of (b/g, -a/g) gives all solutions.

Divisor counting function

If n factors as p1^e1 times p2^e2 and so on, the number of positive divisors is (e1+1)(e2+1)..., the product of one more than each prime exponent.

Divisibility by 11

A number is divisible by 11 exactly when the alternating sum of its digits, taken left to right, is a multiple of 11.

Euclid's lemma

If a prime p divides the product ab, then p divides a or p divides b. This underpins uniqueness of prime factorization.

Vieta's formulas

For ax^2+bx+c=0, the sum of roots is -b/a and the product is c/a. For a cubic ax^3+bx^2+cx+d=0, sum is -b/a and product is -d/a.

Quadratic discriminant

For ax^2+bx+c=0, D=b^2-4ac. Positive D gives two real roots, zero gives a double root, negative gives complex conjugate roots.

AM-GM inequality

For nonnegative reals, the arithmetic mean is at least the geometric mean: (a1+...+an)/n >= (a1...an)^(1/n), with equality iff all terms are equal.

Cauchy-Schwarz inequality

The product of the sums of squares of two real sequences is at least the square of their dot product. Equality holds when the sequences are proportional.

Telescoping sum

A sum whose terms can be written as f(k+1)-f(k) collapses to f(n+1)-f(1). Common for terms like 1/(k(k+1)).

Irrational conjugate roots

If a polynomial with rational coefficients has a root of form a+sqrt(b) with b not a perfect square, then a-sqrt(b) is also a root.

Logarithm product rule

The logarithm of a product equals the sum of the logarithms: log(xy)=log x + log y. Also log(x^k)=k log x and change of base applies.

Sum of roots of polynomial

For a monic polynomial of degree n, the sum of roots equals the negative of the coefficient of x^(n-1). For non-monic, divide by the leading coefficient.

Functional equation strategy

Test constant, linear, and identity candidates; substitute special values like 0, 1, -1; use injectivity or surjectivity to derive constraints on the function.

Inscribed angle theorem

The angle subtended by an arc at the circle's center is twice the angle at any point on the remaining arc. Angles in the same segment are equal.

Cyclic quadrilateral property

A quadrilateral is cyclic iff opposite angles sum to 180 degrees. Equivalently, a pair of opposite angles are supplementary, or the vertices lie on one circle.

Power of a point

For a point P and a circle, the product of distances to two intersection points along any line through P is constant. Tangent length squared equals the secant product.

Heron's formula

The area of a triangle with sides a, b, c and semiperimeter s is sqrt(s(s-a)(s-b)(s-c)). For a cyclic quadrilateral, use sqrt((s-a)(s-b)(s-c)(s-d)).

Ceva's theorem

Cevians AD, BE, CF of a triangle are concurrent exactly when (BD/DC)(CE/EA)(AF/FB)=1. Menelaus' theorem gives a similar product equal to -1 for collinear points.

Centroid ratio

The centroid is the intersection of the medians and divides each median in the ratio 2:1, with the longer segment adjacent to the vertex.

Tangent-chord angle

The angle between a tangent and a chord at the point of tangency equals the angle subtended by that chord in the alternate segment.

Similar triangle area ratio

If two triangles are similar with side ratio k, their areas are in ratio k squared. Corresponding sides are proportional and corresponding angles are equal.

Perpendicular slope condition

Two non-vertical lines are perpendicular exactly when the product of their slopes is -1. Parallel lines have equal slopes.

Combination formula

C(n,r)=n!/(r!(n-r)!) counts unordered selections of r items from n. It satisfies C(n,r)=C(n,n-r).

Pigeonhole principle

If n items are placed into k boxes with n greater than k, some box holds at least two items. In general, some box holds at least ceil(n/k) items.

Inclusion-exclusion principle

For two sets, the union size equals the sum of sizes minus the intersection size. For three sets, add singles, subtract pairwise intersections, add the triple intersection.

Stars and bars

The number of nonnegative integer solutions to x1+...+xk=n is C(n+k-1,k-1). For positive solutions, it is C(n-1,k-1).

Handshake lemma

In any graph, the sum of all vertex degrees equals twice the number of edges. Consequently, the number of vertices with odd degree is even.

Binomial theorem

(x+y)^n expands as the sum over k of C(n,k) x^(n-k) y^k. Setting x=y=1 gives the identity that the binomial coefficients sum to 2^n.

Circular permutation count

The number of distinct arrangements of n people around a round table is (n-1)!, obtained by fixing one person to remove rotational symmetry.