PEI Math 521B cheat sheet

Division Algorithm: for integers a and b with b > 0 there exist unique integers q, r with a = bq + r and 0 ≤ r < b; r = 0 exactly when b divides a.

Euclid's lemma and the Euclidean algorithm: gcd(a, b) = gcd(b, a mod b), and the algorithm terminates because remainders strictly decrease; it yields integers x, y with ax + by = gcd(a, b) (Bézout).

Linear Diophantine equation ax + by = c is solvable in integers iff gcd(a, b) divides c; if (x₀, y₀) is one solution, all solutions are x = x₀ + (b/d)t, y = y₀ − (a/d)t with d = gcd(a, b).

Fundamental Theorem of Arithmetic: every integer n > 1 factors uniquely into primes up to order; consequently the number of divisors is τ(n) = ∏(eᵢ + 1) and the divisor sum is σ(n) = ∏(pᵢ^(eᵢ+1) − 1)/(pᵢ − 1).

Congruence arithmetic: a ≡ b (mod m) iff m divides a − b; congruences may be added and multiplied, but cancellation requires gcd(c, m) = 1. The congruence cx ≡ d (mod m) has a solution iff gcd(c, m) divides d, giving gcd(c, m) classes mod m.

Fermat's little theorem: if p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p); Euler's theorem generalizes it: a^φ(m) ≡ 1 (mod m) whenever gcd(a, m) = 1.

Chinese Remainder Theorem: if m₁, …, mₖ are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has a unique solution modulo the product m₁⋯mₖ; solve by combining two congruences at a time or via Bézout coefficients.

Quadratic residues: for odd prime p, exactly (p−1)/2 nonzero residues are squares mod p; Euler's criterion says a^((p−1)/2) ≡ 1 or −1 mod p according to whether a is a residue, and the Legendre symbol is multiplicative.

Valuation and parity tools: v_p(ab) = v_p(a) + v_p(b), and v_p(n!) = ∑⌊n/p^k⌋ (Legendre's formula); use these to compare prime exponents in divisibility and factorial problems.

Quadratic formula and discriminant: roots of ax² + bx + c are (−b ± √(b² − 4ac))/(2a); the discriminant b² − 4ac determines two real, one repeated, or two complex conjugate roots.

Vieta's formulas: for a monic polynomial with roots r₁, …, rₙ, the sum of roots equals −(coefficient of x^(n−1)) and the product equals (−1)ⁿ times the constant term; symmetric functions of roots can be computed without finding them.

Factor and Remainder Theorem: for polynomial P, P(a) is the remainder on division by x − a, and x − a is a factor iff P(a) = 0; a rational root p/q in lowest terms of an integer polynomial satisfies p | constant term and q | leading coefficient.

Complex numbers: z = a + bi has modulus |z| = √(a² + b²) and conjugate z̄ = a − bi; z z̄ = |z|², and 1/z = z̄/|z|² for z ≠ 0.

De Moivre and roots of unity: (cos θ + i sin θ)ⁿ = cos nθ + i sin nθ; the n-th roots of unity are e^(2πik/n), and they sum to 0 for n > 1.

Logarithm and exponent laws: log_b(xy) = log_b x + log_b y, log_b(x^r) = r log_b x, and change of base log_b x = ln x / ln b; these convert exponential equations into linear ones.

Functional equations: test candidate solutions by substitution; frequent tools are setting variables equal, swapping variables to compare f(x) + f(y) with f(y) + f(x), and checking whether f is forced to be injective or surjective.

Inequalities: AM–GM gives (a₁ + ⋯ + aₙ)/n ≥ (a₁⋯aₙ)^(1/n) for nonnegative reals with equality iff all are equal; Cauchy–Schwarz gives (∑aᵢbᵢ)² ≤ (∑aᵢ²)(∑bᵢ²).

Sequences and series: an arithmetic sequence has aₙ = a₁ + (n−1)d and sum n(a₁ + aₙ)/2; a geometric sequence has aₙ = a₁r^(n−1) and sum a₁(1 − rⁿ)/(1 − r) for r ≠ 1.

Triangle area formulas: A = ½bh = ½ab sin C = √(s(s−a)(s−b)(s−c)) with semiperimeter s = (a + b + c)/2; the circumradius satisfies A = abc/(4R) and the inradius A = rs.

Law of Cosines c² = a² + b² − 2ab cos C and Law of Sines a/sin A = b/sin B = c/sin C = 2R; use the cosine law when given SAS or SSS.

Power of a point: for a point P with secants meeting a circle at distances, PA·PB = PC·PD; if PT is tangent, PT² = PA·PB. This also covers intersecting chords inside the circle.

Cyclic quadrilateral: opposite angles are supplementary, and Ptolemy's theorem states AC·BD = AB·CD + BC·AD for a cyclic quadrilateral ABCD.

Angle chasing: the inscribed angle subtending an arc is half the central angle on the same arc; the angle between a tangent and a chord equals the inscribed angle on the opposite side of the chord.

Similarity and ratios: if two triangles are similar with ratio k, then corresponding lengths scale by k, areas by k², and volumes by k³; AA, SAS, and SSS are the similarity criteria.

Coordinate tools: distance √((x₂−x₁)² + (y₂−y₁)²), midpoint, and slope m = (y₂−y₁)/(x₂−x₁); perpendicular lines satisfy m₁m₂ = −1, and the distance from (x₀, y₀) to ax + by + c = 0 is |ax₀ + by₀ + c|/√(a² + b²).

Circle equation: (x − h)² + (y − k)² = r²; a line meets a circle in 0, 1, or 2 points according to whether the discriminant of the substituted equation is negative, zero, or positive.

Solid measures: sphere volume 4πr³/3 and surface 4πr²; cone and cylinder volumes are (1/3)πr²h and πr²h; prism and pyramid volumes are Bh and Bh/3.

Counting principles: product rule for independent sequential choices, sum rule for disjoint cases; count the complement when 'at least one' conditions appear.

Permutations and combinations: P(n, k) = n!/(n−k)! ordered selections, C(n, k) = n!/(k!(n−k)!) unordered; 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; setting x = y = 1 gives ∑ C(n, k) = 2ⁿ, and setting x = 1, y = −1 gives alternating sums of 0 or 1.

Stars and bars: the number of nonnegative integer solutions of x₁ + ⋯ + xₖ = n is C(n + k − 1, k − 1); for positive solutions it is C(n − 1, k − 1).

Pigeonhole principle: placing N objects in k boxes forces some box to hold at least ⌈N/k⌉ objects; the generalized form is used to force equal residues or repeated values.

Inclusion–exclusion: |A₁ ∪ ⋯ ∪ Aₙ| = ∑|Aᵢ| − ∑|Aᵢ ∩ Aⱼ| + ⋯; it counts objects avoiding all listed properties by taking the complement.

Permutations with repetition: the number of distinct arrangements of a multiset with nᵢ copies of item i is (∑nᵢ)!/(∏ nᵢ!); circular arrangements of n distinct objects number (n − 1)!.

Recurrences: solve linear recurrences by characteristic roots or by telescoping; a first-order recurrence aₙ = raₙ₋₁ + c has closed form aₙ = r^(n−1)a₁ + c(r^(n−1) − 1)/(r − 1) for r ≠ 1.

Graph basics: the sum of degrees equals twice the number of edges; a tree on n vertices has n − 1 edges, and a connected graph on n vertices with n − 1 edges is a tree.

Direct proof structure: assume the hypotheses, unpack definitions, and derive the conclusion in explicit steps; state which definition or theorem justifies each step.

Contrapositive and contradiction: proving ¬Q ⇒ ¬P proves P ⇒ Q; contradiction assumes P and ¬Q and derives an impossibility, and is the standard route for irrationality of √2 and infinitude of primes.

Mathematical induction: base case, then assume the statement for n (or for all values up to n in strong induction) and prove it for n + 1; verify the base case actually covers the first relevant value.

Invariants and monovariants: find a quantity unchanged by every allowed move (parity, sum mod m, coloring count) to prove a configuration is unreachable, or a quantity that strictly changes to prove termination.

Extremal principle: among all counterexamples or configurations choose one with minimal or maximal value, then derive a smaller or larger one to reach a contradiction.

Constructive versus existence proofs: a constructive proof exhibits the object explicitly; a non-constructive proof may use pigeonhole, parity, or intermediate value to show existence without producing the object.

Working backwards and wishful thinking: replace the goal with an equivalent simpler statement, and test small cases (n = 1, 2, 3) to guess the pattern before proving it.

Symmetry and WLOG: when a problem is symmetric in its variables, assume an ordering such as a ≤ b ≤ c to reduce cases, but verify the reduction preserves all possibilities.

Sanity checks: verify units and parity, test boundary cases (zero, negatives, equality cases in inequalities), and confirm that each algebraic manipulation is reversible.