PEI Math 521B flashcards

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

Division Algorithm

For integers a and b with b > 0, there exist unique integers q and r such that a = bq + r with 0 ≤ r < b. The remainder is zero exactly when b divides a.

Euclidean Algorithm

Repeatedly replace the pair (a, b) by (b, a mod b) until the remainder is zero; the last nonzero remainder is gcd(a, b). It also produces Bézout coefficients x, y with ax + by = gcd(a, b).

Bézout's Identity

For integers a and b, not both zero, there exist integers x and y with ax + by = gcd(a, b). Consequently the equation ax + by = c is solvable exactly when gcd(a, b) divides c.

Fundamental Theorem of Arithmetic

Every integer greater than 1 factors into primes, and the factorization is unique up to the order of the factors. This justifies comparing prime exponents to test divisibility and to compute divisor counts.

Chinese Remainder Theorem

If moduli m₁, …, mₖ are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has a solution, and that solution is unique modulo the product of the moduli.

Fermat's Little Theorem

If p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p). Equivalently a^p ≡ a (mod p) for every integer a, which lets you reduce large exponents modulo p − 1.

Euler's Totient Theorem

If gcd(a, m) = 1, then a^φ(m) ≡ 1 (mod m), where φ(m) counts integers from 1 to m coprime to m. For prime m = p this reduces to Fermat's little theorem.

Quadratic Residue Criterion

For an odd prime p and a not divisible by p, a is a square mod p exactly when a^((p−1)/2) ≡ 1 (mod p). Exactly (p−1)/2 nonzero residues are squares.

Vieta's Formulas

For a monic polynomial with roots r₁, …, rₙ, the sum of the roots equals the negative of the x^(n−1) coefficient, and the product equals (−1)ⁿ times the constant term.

Rational Root Theorem

If a polynomial with integer coefficients has a rational root p/q in lowest terms, then p divides the constant term and q divides the leading coefficient. This limits the candidate roots to a finite list.

Factor and Remainder Theorem

For a polynomial P, the remainder on division by x − a equals P(a). Hence x − a is a factor of P exactly when P(a) = 0, which gives a fast factor test.

De Moivre's Theorem

For real θ and integer n, (cos θ + i sin θ)ⁿ = cos nθ + i sin nθ. It computes powers and n-th roots of complex numbers written in polar form.

Roots of Unity

The n-th roots of unity are the numbers e^(2πik/n) for k = 0, 1, …, n − 1. They are the roots of zⁿ − 1, and for n > 1 their sum is zero.

AM–GM Inequality

For nonnegative reals a₁, …, aₙ, the arithmetic mean is at least the geometric mean: (a₁ + ⋯ + aₙ)/n ≥ (a₁⋯aₙ)^(1/n). Equality holds exactly when all terms are equal.

Cauchy–Schwarz Inequality

For real numbers, (∑aᵢbᵢ)² ≤ (∑aᵢ²)(∑bᵢ²). Equality holds when one vector is a scalar multiple of the other; it bounds sums of products in optimization problems.

Geometric Series Sum

A geometric sequence has terms a₁r^(n−1). Its first n terms sum to a₁(1 − rⁿ)/(1 − r) when r ≠ 1, and to n a₁ when r = 1.

Law of Cosines

In a triangle with sides a, b, c and angle C opposite side c, c² = a² + b² − 2ab cos C. It handles SAS and SSS data and reduces to the Pythagorean theorem when C is right.

Law of Sines

In any triangle, a/sin A = b/sin B = c/sin C = 2R, where R is the circumradius. It links side lengths to opposite angles and gives the circumradius directly.

Power of a Point

For a point P and a circle, any secant through P meets the circle at A and B with PA·PB constant. If PT is tangent, then PT² = PA·PB.

Cyclic Quadrilateral Angles

A quadrilateral is cyclic exactly when its opposite angles are supplementary, summing to 180°. Equivalently, two vertices subtending the same segment on the same side give equal angles.

Ptolemy's Theorem

For a cyclic quadrilateral ABCD with vertices in order, the product of the diagonals equals the sum of the products of opposite sides: AC·BD = AB·CD + BC·AD.

Inscribed Angle Theorem

An inscribed angle equals half the central angle subtending the same arc. Angles subtending the same arc from the same side are equal, and an angle subtending a diameter is right.

Similarity Ratios

If two figures are similar with linear ratio k, corresponding lengths scale by k, areas by k², and volumes by k³. Triangles are similar under AA, SAS, or SSS conditions.

Point–Line Distance Formula

The distance from point (x₀, y₀) to the line ax + by + c = 0 is |ax₀ + by₀ + c| divided by √(a² + b²). It is used for tangent and circle-position problems.

Binomial Coefficients

C(n, k) = n!/(k!(n−k)!) counts unordered selections of k items from n. It satisfies C(n, k) = C(n, n−k) and Pascal's identity C(n, k) = C(n−1, k−1) + C(n−1, k).

Binomial Theorem

(x + y)ⁿ = ∑ C(n, k) x^(n−k) y^k. Substituting x = y = 1 yields ∑ C(n, k) = 2ⁿ, the total number of subsets of an n-element set.

Stars and Bars

The number of nonnegative integer solutions of x₁ + ⋯ + xₖ = n is C(n + k − 1, k − 1). Requiring all xᵢ ≥ 1 gives C(n − 1, k − 1) instead.

Pigeonhole Principle

If N objects are placed into k boxes, some box contains at least ⌈N/k⌉ objects. It proves existence of collisions, such as two integers with the same residue modulo m.

Inclusion–Exclusion Principle

The size of a union equals the sum of individual sizes, minus pairwise intersection sizes, plus triple intersections, alternating signs. It counts objects avoiding all listed properties via the complement.

Multiset Permutations

The number of distinct arrangements of n objects with nᵢ identical copies of type i is (∑nᵢ)! divided by the product ∏ nᵢ!. Circular arrangements of n distinct objects number (n − 1)!.

Tree Edge Count

A tree on n vertices has exactly n − 1 edges. Conversely, a connected graph on n vertices with n − 1 edges is a tree, and the degree sum equals twice the edge count.

Proof by Contradiction

To prove statement P, assume P is false and derive an impossibility. Standard uses include proving √2 is irrational and that there are infinitely many primes, by constructing a contradiction.

Mathematical Induction

Prove the base case, then assume the statement for n and derive it for n + 1. Strong induction assumes all cases up to n, which suits recurrences and factorization arguments.

Invariant Argument

An invariant is a quantity unchanged by every allowed operation, such as parity or a sum modulo m. Showing two configurations differ in that quantity proves no sequence of moves connects them.

Extremal Principle

Choose a counterexample or configuration that is minimal or maximal with respect to some measure, then construct a smaller or larger one. The contradiction proves no counterexample exists.