PEI Math 521B key terms

The relation in which an integer a divides an integer b when b = a·k for some integer k, written a | b. It requires exact division with zero remainder and forbids division by zero.

For integers a and b with b > 0, there exist unique integers q and r such that a = bq + r with 0 ≤ r < b. It underlies Euclidean computation and base representation.

An integer greater than 1 whose only positive divisors are 1 and itself. Primes are the multiplicative building blocks of the integers, and every integer above 1 factors uniquely into them.

Every integer greater than 1 can be written as a product of primes, and that factorization is unique up to the order of the factors. It justifies comparing integers through prime exponents.

The largest positive integer dividing both a and b, written gcd(a, b). It can be expressed as an integer combination of a and b, which makes it central to linear Diophantine equations.

A repeated division procedure that computes gcd(a, b) by replacing the pair with (b, r) where r is the remainder of a divided by b. It terminates because remainders strictly decrease.

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

An equation such as ax + by = c requiring integer solutions. It has solutions precisely when gcd(a, b) divides c, and then all solutions form an arithmetic family in one parameter.

The relation a ≡ b (mod n) meaning n divides a − b. Congruence respects addition and multiplication, so arithmetic can be carried out within residue classes modulo n.

The set of all integers congruent to a fixed integer modulo n. The n residue classes partition the integers and form a ring under addition and multiplication modulo n.

An integer x with ax ≡ 1 (mod n). Such an inverse exists exactly when gcd(a, n) = 1, and it can be found using the extended Euclidean algorithm.

If moduli are pairwise coprime, a system of congruences with one unknown has a unique solution modulo the product of the moduli. It converts one hard congruence into several easier ones.

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, a key tool for reducing large exponents.

The function φ(n) counting integers from 1 to n that are coprime to n. It satisfies φ(p) = p − 1 for primes and is multiplicative over coprime factors, enabling Euler's theorem.

A set with an associative binary operation, an identity element, and an inverse for every element. Groups capture symmetry and invertible structure and are the central object of abstract algebra.

A nonempty subset of a group that is closed under the operation and under taking inverses, hence is itself a group. A subset H is a subgroup exactly when a, b in H implies ab⁻¹ in H.

In a finite group, the order of any subgroup divides the order of the group. A consequence is that the order of any element divides the group order, restricting possible subgroup sizes.

A translate aH = {ah : h in H} of a subgroup H in a group G. Left cosets of H partition G, all have the same size as H, and their number is the index of H.

A subgroup H of G satisfying gHg⁻¹ = H for every g in G. Normality is exactly the condition needed for the set of cosets to form a quotient group under the induced operation.

The group G/N whose elements are the cosets of a normal subgroup N, with multiplication (aN)(bN) = abN. It records the structure of G after collapsing N to the identity.

A map between groups preserving the operation, so f(ab) = f(a)f(b). Its kernel measures what is collapsed and its image measures what is reached; both are subgroups.

A bijective homomorphism between algebraic structures, whose inverse is also a homomorphism. Isomorphic groups share all structural properties, so they are regarded as the same abstract group.

A group generated by a single element g, consisting of all powers of g. Every cyclic group is abelian, and a finite cyclic group of order n is isomorphic to the integers modulo n.

A bijection from a finite set to itself, commonly written in cycle notation. Permutations form the symmetric group, and every permutation decomposes uniquely into disjoint cycles.

A commutative ring in which every nonzero element has a multiplicative inverse. Fields such as the rationals, reals, and integers modulo a prime support division and linear algebra.

The set of polynomials in one variable over a ring, with coefficientwise addition and convolution multiplication. Over a field it satisfies a division algorithm, giving unique factorization and root-factor correspondence.

For a polynomial f over a field and a scalar a, (x − a) divides f exactly when f(a) = 0. It converts root-finding into linear factorization and bounds the number of roots by the degree.

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. It narrows candidate roots to finitely many values.

Two triangles whose corresponding sides and angles are equal, established by criteria such as SSS, SAS, ASA, and AAS. Congruence transfers all measurements from one triangle to the other.

Triangles with equal corresponding angles, whose corresponding sides are then proportional. Similarity preserves ratios and angles, enabling indirect measurement and power-of-a-point arguments.

An angle inscribed in a semicircle is a right angle. More generally, an inscribed angle equals half the measure of the arc it intercepts, a cornerstone of circle geometry.

An angle whose vertex lies on a circle equals half the central angle subtending the same arc. Angles subtending the same arc from the same side are therefore equal.

A quadrilateral whose four vertices lie on one circle. Its opposite angles are supplementary, and conversely a quadrilateral with supplementary opposite angles is cyclic.

For a point P and circle, the quantity PA·PB computed along any secant through P. It equals the squared tangent length when P is outside, and is constant for all lines through P.

A ray from a vertex dividing an angle into two equal parts. The angle bisector theorem states it cuts the opposite side in the ratio of the adjacent sides.

For cevians from the vertices of a triangle meeting the opposite sides at D, E, F, the three are concurrent exactly when the product of the three side ratios equals 1. It certifies concurrence.

If more than n objects are placed into n boxes, some box holds at least two objects. The generalized form guarantees a box with at least the ceiling of objects divided by boxes.

An ordered arrangement of distinct objects; the number of arrangements of k objects chosen from n is n!/(n−k)!. Order matters, distinguishing permutations from combinations.

A selection of objects where order is irrelevant; choosing k from n gives C(n, k) = n!/(k!(n−k)!). It counts subsets of a fixed size and appears in binomial expansions.

The number C(n, k) counting k-element subsets of an n-element set. It satisfies Pascal's identity C(n, k) = C(n−1, k−1) + C(n−1, k) and appears in the binomial theorem.

Counting objects by subtracting the number of objects failing a condition from the total. It simplifies problems where the forbidden cases are easier to enumerate than the desired ones.

A proof strategy that selects a maximal or minimal object among those satisfying a condition and derives a contradiction or structure from its extremality. It often resolves existence questions elegantly.

A quantity unchanged by every allowed operation or move in a process. Finding an invariant proves certain configurations unreachable by showing target and start differ on it.

A quantity that changes in only one direction under each allowed move, such as strictly decreasing. Its boundedness guarantees termination and can bound the number of possible moves.

A proof technique establishing a base case and then showing the statement for n implies it for n+1. Strong induction permits assuming all earlier cases to prove the next one.

A method that assumes the negation of the claim and derives an impossibility, thereby establishing the claim. It is especially effective for irrationality and infinitude results.

Every nonempty set of nonnegative integers has a least element. It is logically equivalent to induction and supports minimal-counterexample proofs by isolating a smallest failure.

The symbols ∀ (for all) and ∃ (there exists) expressing the scope of a variable in a statement. Their order matters: ∀x∃y differs from ∃y∀x, and negation swaps them.

A proof that derives the conclusion from the hypotheses through a chain of valid implications. It is the default strategy before considering contradiction or contraposition.