Math 103B Final Vocab + Concepts Review

Binary Operation

A rule that takes two elements from a set and combines them to get another element that's still in the same set. Think of it like addition on the integers — add any two integers and you still get an integer. The key word is "closure": the result stays in your set.

Group

A set with an operation that satisfies three rules: (1) the operation is associative (parentheses don't matter), (2) there's an identity element that does nothing (like 0 for addition), and (3) every element has an inverse. If the operation also commutes (order doesn't matter), we call it abelian.

Abelian Group

A group where the order of the operation doesn't matter — $a * b = b * a$ for everything in the group. Think of integers under addition: $3 + 5 = 5 + 3$. All additive groups you encounter in ring theory will be abelian.

Subgroup

A subset of a group that is itself a group under the same operation. To check, make sure it contains the identity, is closed under the operation, and contains inverses of all its elements. For example, the even integers are a subgroup of the integers under addition.

Order of a Group

Just the number of elements in the group. So $|\mathbb{Z}_{12}| = 12$, and $|S_3| = 6$.

Order of an Element

The smallest positive integer $n$ such that applying the group operation to the element $n$ times gives the identity. A key fact: in any finite group, the order of every element divides the size of the group (Lagrange's Theorem). This is what powers Fermat's Little Theorem.

Group Homomorphism

A function between two groups that "respects" the group operation — it doesn't matter if you operate first and then apply the function, or apply the function first and then operate. If it's also a bijection (one-to-one and onto), it's called an isomorphism, meaning the two groups are structurally the same.

Symmetric Group $S_n$

The group of all ways to rearrange (permute) the numbers $\{1, 2, \ldots, n\}$, where the operation is composition. It has $n

Dihedral Group $D_n$

The group of symmetries of a regular $n$-sided polygon — includes $n$ rotations and $n$ reflections, for $2n$ elements total. It's non-commutative for $n \geq 3$.

$GL(2, \mathbb{R})$

The "general linear group" — all $2 \times 2$ invertible real matrices under matrix multiplication. Non-commutative, since matrix multiplication order matters.

$SL(2, \mathbb{R})$

The "special linear group" — the subgroup of $GL(2,\mathbb{R})$ consisting of matrices with determinant exactly 1. It's a subgroup of $GL(2,\mathbb{R})$.

Cyclic Group

A group generated by a single element — every element in the group is just a power of one special element $g$. We write $G = \langle g \rangle$. Any finite cyclic group of size $n$ is isomorphic to $\mathbb{Z}_n$.

Quotient Group

When $H$ is a normal subgroup of $G$, you can form the quotient group $G/H$ whose elements are the cosets of $H$. You "add" cosets by adding representatives. This is the group theory version of what we do with quotient rings.

Fundamental Theorem of Finitely Generated Abelian Groups

Every finitely generated abelian group can be broken down as a direct product of cyclic groups. This is how we classify unit groups of finite fields — they always turn out to be cyclic.

Ring

A set with two operations (addition and multiplication) where: addition makes it an abelian group, multiplication is associative, and the distributive law holds. Multiplication doesn't have to be commutative and there doesn't have to be a multiplicative identity.

Additive Identity (Zero Element)

The element $0$ in a ring such that $a + 0 = a$ for everything in the ring. Every ring has exactly one of these. Also note that $0 \cdot a = 0$ for everything — zero absorbs multiplication.

Additive Inverse

For every element $a$ in a ring, its additive inverse $-a$ satisfies $a + (-a) = 0$. This is what lets us define subtraction: $a - b = a + (-b)$.

Multiplicative Identity (Unity)

An element $1$ in a ring such that $1 \cdot a = a \cdot 1 = a$ for everything in the ring. Not every ring has one — but when it does (and $1 \neq 0$), we call it the unity and say it's a "ring with unity."

Commutative Ring

A ring where multiplication commutes: $ab = ba$ for all elements. Most of the rings we work with are commutative — integers, rationals, $\mathbb{Z}_n$, polynomials over a field. A key non-example is the ring of $n \times n$ matrices.

Ring with Unity

A ring that has a multiplicative identity $1 \neq 0$. The unity is unique. Example: $\mathbb{Z}$ has unity 1; $M_n(\mathbb{R})$ has unity equal to the identity matrix. Non-example: $2\mathbb{Z}$ (even integers) has no multiplicative identity.

Subring

A subset of a ring that is itself a ring under the same two operations. Check: it's closed under subtraction and multiplication, and contains 0. Warning: a subring of a ring with unity doesn't have to share the same unity.

Direct Product of Rings

Given two rings $R$ and $S$, you can form $R \times S$ by doing operations coordinatewise: add or multiply component by component. For example, $\mathbb{Z}_{15} \cong \mathbb{Z}_3 \times \mathbb{Z}_5$ as rings (since $\gcd(3,5) = 1$).

Ring Homomorphism

A function between two rings that preserves both addition and multiplication. It always sends 0 to 0, but it doesn't necessarily send 1 to 1. Examples: reducing integers mod $n$, or plugging a value into a polynomial (evaluation).

Ring Isomorphism

A ring homomorphism that is also a bijection. If one exists between $R$ and $S$, we write $R \cong S$ and say they're "the same ring." Warning: two rings can be isomorphic as groups (under addition) but not as rings — like $\mathbb{Z}$ and $2\mathbb{Z}$.

Kernel of a Ring Homomorphism

The set of all elements that get sent to 0 by the homomorphism. The kernel is always an ideal (not just a subring). For example, the kernel of the map $\mathbb{Z} \to \mathbb{Z}_m$ is $m\mathbb{Z}$ (all multiples of $m$).

Evaluation Homomorphism

The ring homomorphism $\varphi_\alpha: R[x] \to S$ that just plugs in $\alpha$ for $x$. It's a ring homomorphism because substituting a value distributes over addition and multiplication. "Solving $f(x) = 0$" literally means finding $\alpha$ where this homomorphism sends $f$ to 0.

Unit

An element $u$ in a ring with unity that has a multiplicative inverse — some element $u^{-1}$ such that $u \cdot u^{-1} = 1$. Units are the elements you can "divide by." In $\mathbb{Z}$ the only units are $\pm 1$. In $\mathbb{Z}_5$, every nonzero element is a unit.

Multiplicative Inverse

Given a unit $u$, its inverse $u^{-1}$ is the unique element satisfying $u \cdot u^{-1} = 1$. Uniqueness: if $ux = uy = 1$, you can show $x = y$ by multiplying both sides by $u^{-1}$.

Unit Group

The set of all units in a ring with unity, denoted $R^\times$. It forms a group under multiplication. Euler's theorem and Fermat's Little Theorem are really just statements about the structure of $\mathbb{Z}_n^\times$.

Zero Divisor

A nonzero element $a$ in a ring where there's some other nonzero element $b$ with $ab = 0$. These break the usual "cancellation law" — you can't always cancel a common factor. Example in $\mathbb{Z}_{10}$: $2 \cdot 5 = 0$, so both 2 and 5 are zero divisors. Units can never be zero divisors.

Cancellation Law

In an integral domain (no zero divisors), if $ac = bc$ and $c \neq 0$, then $a = b$. This is just like normal arithmetic. It fails in rings with zero divisors — e.g., in $\mathbb{Z}_{10}$, $2 \cdot 5 = 4 \cdot 5 = 0$ but $2 \neq 4$.

Zero Product Property

In an integral domain, if a product of elements equals zero, at least one of them must be zero. This is the generalization of the familiar "if $ab = 0$ then $a = 0$ or $b = 0$" to any number of factors.

Nilpotent Element

An element $x$ in a ring such that some power $x^n = 0$. For example, $2 \in \mathbb{Z}_4$ is nilpotent since $2^2 = 4 = 0$ in $\mathbb{Z}_4$. Fields and integral domains have no nonzero nilpotent elements.

Idempotent Element

An element $e$ where $e^2 = e$. Zero and the unity are always idempotent. In $\mathbb{Z}_6$, the elements 0, 1, 3, and 4 are all idempotent.

Characteristic of a Ring

The smallest positive integer $n$ such that adding 1 to itself $n$ times gives 0. If no such $n$ exists, the characteristic is 0. For example, $\mathbb{Z}$ has characteristic 0, $\mathbb{Z}_n$ has characteristic $n$, and any field $\mathbb{F}_{p^k}$ has characteristic $p$ (a prime).

Field

A commutative ring with unity where every nonzero element is a unit (has a multiplicative inverse). It's the setting where you can freely add, subtract, multiply, and divide (by nonzero elements). Examples: $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$, $\mathbb{Z}_p$ for prime $p$.

Integral Domain

A commutative ring with unity and no zero divisors — if $ab = 0$, then $a = 0$ or $b = 0$. Every field is an integral domain, but not every integral domain is a field ($\mathbb{Z}$ is an integral domain but 2 has no inverse). A key theorem: every finite integral domain is a field.

The Ring Hierarchy

From most general to most specific: Rings ⊃ Commutative Rings with Unity ⊃ Integral Domains ⊃ Fields. Each step adds a requirement. $\mathbb{Z}$ is an integral domain but not a field. $\mathbb{Q}$ is a field. $M_2(\mathbb{R})$ is a ring with unity but not commutative. $2\mathbb{Z}$ is a commutative ring but has no unity.

Integers Modulo $n$ ($\mathbb{Z}_n$)

The ring $\{0, 1, \ldots, n-1\}$ where you do arithmetic mod $n$. It's a commutative ring with unity for all $n$, but it's a field if and only if $n$ is prime (since that's when every nonzero element is coprime to $n$, hence a unit).

Congruence / Modular Arithmetic

We say $a \equiv b \pmod{n}$ if $n$ divides $a - b$. This partitions all the integers into $n$ buckets (residue classes), which are exactly the elements of $\mathbb{Z}_n$.

Greatest Common Divisor (gcd)

The largest positive integer that divides both $a$ and $b$. We call $a$ and $b$ "coprime" (or "relatively prime") if their gcd is 1 — they share no common factors.

Euclidean Algorithm

A procedure to find $\gcd(a, b)$ by repeatedly dividing and taking remainders until you hit 0. The last nonzero remainder is the gcd. Running it backwards lets you write the gcd as a combination $ax + by$, which gives you Bézout's Identity.

Bézout's Identity

If $d = \gcd(a, b)$, there exist integers $x, y$ such that $ax + by = d$. The key application: if $\gcd(a, n) = 1$, you can find $x$ such that $ax \equiv 1 \pmod{n}$ — that's the multiplicative inverse of $a$ in $\mathbb{Z}_n$.

Multiplicative Inverse in $\mathbb{Z}_n$

An element $a \in \mathbb{Z}_n$ has a multiplicative inverse if and only if $\gcd(a, n) = 1$. You find it using the extended Euclidean algorithm (Bézout). The inverse is unique mod $n$.

Units in $\mathbb{Z}_n$

Every nonzero element of $\mathbb{Z}_n$ is either a unit (if $\gcd(a, n) = 1$) or a zero divisor (if $\gcd(a, n) > 1$). This neatly splits all nonzero elements into two camps. Consequence: $\mathbb{Z}_n$ is a field if and only if $n$ is prime.

Euler Phi Function $\varphi(n)$

Counts how many integers from 1 to $n$ are coprime to $n$ — equivalently, the size of $\mathbb{Z}_n^\times$. Key formulas: $\varphi(p) = p-1$ for prime $p$; $\varphi(p^k) = p^k - p^{k-1}$; and it's multiplicative: $\varphi(mn) = \varphi(m)\varphi(n)$ when $\gcd(m,n) = 1$.

Fermat's Little Theorem

If $p$ is prime and $p$ doesn't divide $a$, then $a^{p-1} \equiv 1 \pmod{p}$. This follows from the fact that $\mathbb{Z}_p^\times$ has order $p-1$, combined with Lagrange's Theorem. Useful trick: to compute $a^k \pmod{p}$, reduce the exponent $k$ modulo $p-1$.

Euler's Theorem

For any $n$ and any $a$ coprime to $n$: $a^{\varphi(n)} \equiv 1 \pmod{n}$. This is the generalization of Fermat's Little Theorem to non-prime moduli. Same useful trick: reduce exponents mod $\varphi(n)$ when computing powers.

Primitive Root

A generator of the unit group $\mathbb{Z}_n^\times$ — a single element $g$ such that every unit mod $n$ is a power of $g$. Primitive roots exist when $n = 1, 2, 4, p^k$, or $2p^k$ for an odd prime $p$.

Complete Residue System

A set of integers containing exactly one representative from each residue class mod $m$. In other words, a set that hits each of $\{0, 1, \ldots, m-1\}$ exactly once after reducing mod $m$.

Chinese Remainder Theorem (CRT)

If $m$ and $n$ are coprime, then $\mathbb{Z}_{mn} \cong \mathbb{Z}_m \times \mathbb{Z}_n$ as rings. Concretely: any system of two congruences with coprime moduli has a unique solution mod $mn$. Used in RSA and in understanding unit groups.

Public-Key Cryptography

A system that uses two related keys: a public key (shared openly, for encrypting) and a private key (kept secret, for decrypting). Anyone can encrypt a message, but only the key owner can decrypt it.

RSA Cryptosystem

A public-key encryption scheme based on modular exponentiation. Alice picks two large primes $p$ and $q$, sets $n = pq$, and chooses an exponent $e$ coprime to $\varphi(n)$. Her public key is $(n, e)$. To encrypt a message $m$, compute $c = m^e \pmod{n}$. To decrypt, use the private key $d = e^{-1} \pmod{\varphi(n)}$ and compute $c^d \pmod{n}$. Security relies on how hard it is to factor large numbers.

Public Key (RSA)

The pair $(n, e)$ in RSA, where $n = pq$ is a product of two large primes and $e$ is chosen coprime to $\varphi(n)$. Shared openly so anyone can encrypt messages to you.

Private Key (RSA)

The exponent $d = e^{-1} \pmod{\varphi(n)}$ in RSA. Kept secret; used to decrypt incoming messages.

Semiprime

The product of exactly two primes. In RSA, $n = pq$ is a semiprime. The security of RSA relies on the computational difficulty of factoring $n$ back into $p$ and $q$.

Fermat Factorization

A method to factor $n = pq$ by writing $n = x^2 - y^2$ and guessing $x$ starting from $\lceil\sqrt{n}\rceil$. It's fast when $p$ and $q$ are close together — which is why RSA primes should be chosen far apart

Shor's Algorithm

A quantum algorithm that can factor integers efficiently, which would break RSA. On classical computers, no efficient factoring algorithm is known. This motivates "post-quantum cryptography."

Field of Fractions

Given an integral domain $D$, its field of fractions $\text{Frac}(D)$ is the smallest field containing $D$. You build it by formally creating fractions $a/b$ (with $b \neq 0$) and saying two fractions are equal if they cross-multiply to the same thing. Examples: $\text{Frac}(\mathbb{Z}) = \mathbb{Q}$, and $\text{Frac}(\mathbb{R}[x]) = \mathbb{R}(x)$, the rational functions.

Equivalence Relation on Fractions

The relation that says $a/b \sim c/d$ if $ad = bc$. This is the formal way to say two fractions are the same. It's reflexive, symmetric, and transitive — and the transitive part requires the integral domain property (no zero divisors).

Rational Functions

The field of fractions of $F[x]$ — all formal ratios $f(x)/g(x)$ where $g(x) \neq 0$. Think of expressions like $\frac{x^2 + 1}{x^3 - x}$.

Polynomial Ring $R[x]$

The set of all polynomials with coefficients in $R$, under the usual polynomial addition and multiplication. If $R$ is commutative, so is $R[x]$; if $R$ has a unity, so does $R[x]$.

Indeterminate

In $R[x]$, the symbol $x$ is not a variable you plug numbers into — it's just a formal placeholder that keeps track of coefficient positions. Two polynomials are equal if and only if all their coefficients match.

Degree

The index of the highest nonzero term in a polynomial. So $\deg(3x^5 + 2x + 1) = 5$. The zero polynomial has undefined degree. Key fact in integral domains: $\deg(fg) = \deg f + \deg g$. This can fail in rings with zero divisors.

Leading Coefficient

The coefficient of the highest-degree term in a polynomial. For $f(x) = 3x^5 + \ldots$, the leading coefficient is 3.

Monic Polynomial

A polynomial whose leading coefficient is 1. So $x^3 + 2x + 1$ is monic; $3x^2 + 1$ is not.

Constant Polynomial

A polynomial of degree 0 — just a nonzero element of the base ring, with no $x$ terms.

Units in Polynomial Rings

Over an integral domain, the only units in $R[x]$ are the nonzero constant polynomials that are units in $R$. No polynomial of positive degree can be a unit (degree argument). Over a non-integral-domain, weird things can happen — e.g., $4x + 1$ is a unit in $\mathbb{Z}_8[x]$.

Root / Zero of a Polynomial

An element $\alpha$ such that plugging it into the polynomial gives 0. Same as saying the evaluation homomorphism $\varphi_\alpha$ sends $f$ to 0.

Division Algorithm for Polynomials

Over a field $F$, for any polynomials $f(x)$ and $g(x) \neq 0$, you can uniquely write $f(x) = q(x)g(x) + r(x)$ where the remainder $r(x)$ has smaller degree than $g(x)$ (or is zero). This is literally polynomial long division. Requires a field so you can divide leading coefficients.

Factor Theorem

Over a field, $a$ is a root of $f(x)$ if and only if $(x - a)$ divides $f(x)$. It follows directly from the polynomial division algorithm.

Bound on Number of Roots

A nonzero polynomial of degree $n$ over a field has at most $n$ roots. This can fail over rings with zero divisors — $x^2 - 1$ has 4 roots in $\mathbb{Z}_8$

Polynomial Interpolation Corollary

If two polynomials of degree $\leq n$ agree at $n+1$ distinct points over a field, they must be the same polynomial. Follows from the bound on roots.

Irreducible Polynomial

A polynomial that can't be factored into two polynomials of smaller degree (over the same field). Irreducible polynomials are the "primes" of the polynomial ring. Important: irreducibility depends on the field — $x^2 - 2$ is irreducible over $\mathbb{Q}$ but factors over $\mathbb{R}$.

Reducible Polynomial

A polynomial that CAN be factored into two polynomials of smaller degree. It's the opposite of irreducible.

Reducibility Criterion for Degree 2 or 3

A degree-2 or degree-3 polynomial over a field is reducible if and only if it has a root. This is because any factorization must include a degree-1 factor (which corresponds to a root). Warning: this fails for degree 4 and higher

Cyclic Unit Group of Finite Fields

The multiplicative group of any finite field is always cyclic. That is, there's always a single element whose powers give you every nonzero element of the field.

Rational Root Theorem

For a polynomial $f(x)$ with integer coefficients, any rational root $p/q$ (in lowest terms) must satisfy: $p$ divides the constant term and $q$ divides the leading coefficient. Use this to get a finite list of candidates to test.

Gauss's Lemma

If a polynomial with integer coefficients factors over $\mathbb{Q}$, it already factors over $\mathbb{Z}$ (with factors of the same degrees). So to check irreducibility over $\mathbb{Q}$, you can work with integer coefficients — very handy

Eisenstein's Criterion

A test for irreducibility over $\mathbb{Q}$: if there's a prime $p$ such that $p$ divides all non-leading coefficients, $p$ does NOT divide the leading coefficient, and $p^2$ does NOT divide the constant term — then the polynomial is irreducible over $\mathbb{Q}$. Example: $x^2 - 2$ is irreducible by Eisenstein with $p = 2$.

Reduction Modulo $p$ (Irreducibility Test)

If you reduce all coefficients of $f(x) \in \mathbb{Z}[x]$ mod $p$ (without the degree dropping) and the result is irreducible over $\mathbb{Z}_p$, then $f(x)$ is irreducible over $\mathbb{Q}$.

Cyclotomic Polynomial

The polynomial $\Phi_p(x) = x^{p-1} + x^{p-2} + \cdots + x + 1$ for a prime $p$. Its roots are the primitive $p$-th roots of unity $e^{2\pi i k/p}$. It is always irreducible over $\mathbb{Q}$.

Ideal

A subset $I$ of a ring $R$ that is a subgroup under addition AND has the "absorption" property: multiply anything in $I$ by any element of $R$ and the result is still in $I$. Think of $I$ as "sticky" — once you're in $I$, multiplying by anything from outside stays in $I$. Example: $n\mathbb{Z}$ (multiples of $n$) is an ideal in $\mathbb{Z}$.

Sticky Property (Absorption Property)

The key property of ideals beyond being a subgroup: for all $r \in R$ and $x \in I$, the products $rx$ and $xr$ stay in $I$. This is what makes quotient ring multiplication well-defined.

Trivial Ideal

The ideal $\{0\}$ — just the zero element. Every ring has this. Also called the zero ideal.

Improper Ideal

The ideal $R$ — the whole ring itself. Every ring is an ideal of itself. An ideal that's not the whole ring is called a proper ideal.

Principal Ideal

The ideal $(a) = \{ra : r \in R\}$ generated by a single element $a$. It's the smallest ideal containing $a$. Examples: $(n) = n\mathbb{Z}$ in $\mathbb{Z}$; $(x^2 + 1)$ in $\mathbb{R}[x]$ is all multiples of $x^2 + 1$.

Principal Ideal Domain (PID)

An integral domain where every ideal is principal (generated by a single element). Both $\mathbb{Z}$ and $F[x]$ (for any field $F$) are PIDs. In a PID you don't need multiple generators — one element always suffices.

Non-Principal Ideal

An ideal that cannot be generated by a single element. Example: the ideal $(2, x)$ in $\mathbb{Z}[x]$ — polynomials with even constant term. No single polynomial generates this.

Kernel as an Ideal

The kernel of any ring homomorphism $\varphi: R \to S$ is always an ideal of $R$ (not just a subring). This is because the absorption property follows from $\varphi(r)\varphi(x) = \varphi(r) \cdot 0 = 0$.

Coset (in a Ring)

For an ideal $I$ and element $a \in R$, the coset $a + I = \{a + i : i \in I\}$. Two cosets $a + I$ and $b + I$ are equal exactly when $a - b \in I$.

Quotient Ring

Given a ring $R$ and ideal $I$, the quotient ring $R/I$ has elements that are cosets $a + I$, with coset addition and multiplication defined in the obvious way. The sticky property of $I$ ensures multiplication is well-defined. Classic examples: $\mathbb{Z}/m\mathbb{Z} \cong \mathbb{Z}_m$, and $\mathbb{R}[x]/(x^2+1) \cong \mathbb{C}$.

Well-Defined (Quotient Multiplication)

Multiplication in a quotient ring is "well-defined" if the result doesn't depend on which coset representative you pick. The sticky property of ideals is exactly what guarantees this: if $a' = a + i$ and $b' = b + j$ for $i, j \in I$, the extra terms $aj + ib + ij$ all land back in $I$.

First Isomorphism Theorem for Rings

If $\varphi: R \to S$ is a surjective ring homomorphism, then $R/\ker\varphi \cong S$. The strategy: to identify a quotient ring, find a surjective homomorphism onto something you recognize and compute the kernel.

Maximal Ideal

A proper ideal $M \subsetneq R$ such that no ideal sits strictly between $M$ and $R$. It's as big as a proper ideal can get. The key theorem: $M$ is maximal if and only if $R/M$ is a field.

Prime Ideal

A proper ideal $I$ such that whenever $ab \in I$, at least one of $a$ or $b$ is in $I$. Mirrors how prime numbers work: if $p \mid ab$ then $p \mid a$ or $p \mid b$. Key theorem: $I$ is prime if and only if $R/I$ is an integral domain.

Maximal Implies Prime

Every maximal ideal is a prime ideal. Proof: if $M$ is maximal, $R/M$ is a field, and every field is an integral domain, so $M$ is prime. The converse is FALSE — prime ideals don't have to be maximal.

Ideals Containing a Unit

If an ideal $I$ contains any unit, then $I = R$ (the whole ring). So proper ideals can never contain units. Corollary: a field has no proper nontrivial ideals at all.

Ideals in $F[x]$ are Principal

Every ideal in $F[x]$ (for a field $F$) is generated by a single polynomial — the one of smallest degree in the ideal. This follows from the polynomial division algorithm.

Irreducible iff Maximal (in $F[x]$)

An ideal $(f(x))$ in $F[x]$ is maximal if and only if $f(x)$ is irreducible. So irreducible polynomials $\leftrightarrow$ maximal ideals, and $F[x]/(f(x))$ is a field exactly when $f(x)$ is irreducible.