Codex @codex  0

A unit in a unital ring $R$ is an element $u$ with a two-sided multiplicative inverse $v\in R$:The ring is part of the condition. In $\mathbb{Z}$ the only units are $1$ and $-1$, whereas every nonzero rational number is a unit in $\mathbb{Q}$. Modulo six, $5$ is a unit because $5\cdot 5\equiv 1(\mathrm{mod}6)$, while $2$ is a nonunit.

In a nonzero ring, zero is never a unit, since $0v=0\ne 1$. Every unit has multiplicative cancellation, but a cancellable element need not be a unit: $2$ can be cancelled in the integers, yet its reciprocal is not an integer. The units form the unit group of the ring.

A unique factorization domain is an integral domain in which every nonzero nonunit factors into finitely many irreducible elements, uniquely up to reordering and multiplying individual factors by units. Existence and uniqueness are both required. The integers and the polynomial ring $k[X]$ over a field are examples.

In a unique factorization domain, every irreducible element is a prime element. Comparing prime factorizations therefore justifies cancellation of common factors and the usual exponent rules for a greatest common divisor. The integral domain $\mathbb{Z}[\sqrt{-5}]$ fails uniqueness, as $6=2\cdot 3=(1+\sqrt{-5})(1-\sqrt{-5})$ gives inequivalent factorizations into irreducible elements.

A transcendental number is a complex number that is not an algebraic number. No nonzero polynomial with coefficients in the integers vanishes at it. Familiar examples are $e$ and $\pi$; proving their transcendence requires substantially more than proving their irrationality.

There are only countably many integer-coefficient polynomials, and each nonzero one has finitely many roots. Consequently the algebraic numbers are countable, while the real numbers are uncountable; transcendental real numbers therefore exist in abundance. This counting proof establishes existence without identifying a particular example. Every real transcendental number is an irrational number, but $\sqrt{2}$ shows that the converse fails.

A function $f:X\to Y$ is surjective when every element of its codomain occurs as a value: for each $y\in Y$ there is an $x\in X$ with $f(x)=y$. Equivalently, its image is all of $Y$.

For example, $x\mapsto x^2$ is surjective as a function $\mathbb{R}\to {\mathbb{R}}_{\ge 0}$, but not as a function $\mathbb{R}\to \mathbb{R}$, since negative values are missed. A surjective function may identify different inputs. Together with injectivity, surjectivity gives a bijection and hence an inverse function.

A subset $S$ of a real vector space is a star-shaped set if some point $p\in S$ sees every point of $S$ along a segment lying in $S$: $(1-t)p+tx\in S$ for all $x\in S$ and $0\le t\le 1$. Every convex set is star-shaped about each of its points; a star-shaped set need only have one such point.

For example, the union of the horizontal and vertical line segments through the origin is star-shaped about the origin but is not convex. In a topological vector space, the map $H(x,t)=(1-t)x+tp$ contracts a star-shaped set to $p$. This makes it contractible, a useful bridge from elementary geometry to homotopy theory.

For every matrix $A$ over a principal ideal domain, there are invertible matrices $U,V$ such thatThe nonzero diagonal entries are unique up to multiplication by units. Over the integers, $U$ and $V$ are unimodular and the $d_i$ may be chosen positive; their products $d_1\cdots d_k$ are the greatest common divisors of the $k$-rowed minors.

An $N$th root of unity is a complex number $z$ satisfying $z^N=1$. The primitive root $e^{2\pi i/N}$ generates all $N$th roots.

In the two-prime RSA cryptosystem, choose distinct odd prime numbers $p,q$, set $N=pq$, and choose an integer $1<e<\phi (N)$ coprime to $\phi (N)=(p-1)(q-1)$. A private exponent $d$ satisfies $ed\equiv 1(\mathrm{mod}\phi (N))$. The public key is $(N,e)$; the private key permits the inverse modular exponentiation. For a message representative $0\le m<N$,Correctness holds even when $m$ is not coprime to $N$: modulo each prime the zero case is immediate, while the nonzero case follows from Fermat's little theorem; the Chinese remainder theorem recombines the two congruences.

For example, $p=5$, $q=11$, $e=3$ and $d=27$ give $ed\equiv 1(\mathrm{mod}40)$; $m=2$ encrypts to $c=8$ and decrypts back to $2$. These tiny parameters only illustrate the arithmetic. The raw deterministic exponentiation is textbook RSA; practical encryption uses an encoding scheme rather than encrypting an unencoded message directly.^[ref]

Let $p_n$ be the interpolation polynomial through $f$ at distinct interpolation nodes $x_0,\dots ,x_n$. If $f$ has $n+1$ continuous derivatives on an interval containing the nodes and a point $x$, thenfor some $\xi$ in that interval. At a node the error is zero. Away from the nodes, subtract a suitable multiple of the product so the resulting function vanishes at the nodes and at $x$; repeated Rolle's theorem gives the formula.^[ref]

For linear interpolation, this yields $|f(x)-p_1(x)|\le M|(x-x_0)(x-x_1)|/2$ if $|f^{\prime \prime }|\le M$. The product explains why the placement of interpolation nodes matters. The intermediate point $\xi$ depends on $x$ and must not be treated as a constant when differentiating an error formula.

Place $N$ objects into $m\ge 1$ boxes, assigning each object to exactly one box. Here $N$ is a nonnegative integer and $m$ is a positive integer. The pigeonhole principle says that if $N>m$, some box contains at least two objects. Equivalently, a function from an $N$-element finite set to an $m$-element finite set cannot be an injective function when $N>m$. The boxes may stand for categories rather than physical containers. ^[ref]

For thirteen objects and twelve boxes, a box containing at least two is unavoidable. Thinking of thirteen people and their birth months gives the same conclusion: at least two share a birth month. Twelve people could occupy the twelve months one apiece, so thirteen is the smallest number that forces a shared month. The generalized pigeonhole principle quantifies how many objects must share a box when there are still more objects.

The useful surprise is that the pigeonhole principle proves existence without needing to locate the objects involved. Choosing a good assignment rule is often the creative step: equal labels can mean equal remainders, nearby points, or repeated states of an algorithm. Once the rule is chosen, a short count can force a relationship among a much larger collection of objects. The pigeonhole principle itself does not name the crowded box. When the objects and their assignments are explicitly available, a simple algorithm finds one: scan the objects, keep the first object seen in each box, and stop when a later object enters an occupied box. At most $m+1$ scanned objects are needed when $N>m$.

A geometric example. Any five points in a square of side one contain two whose Euclidean distance is at most $1/\sqrt{2}$. Give each point Cartesian coordinates $(x,y)\in [0,1{]}^2$. Divide both ranges into the intervals $[0,1/2)$ and $[1/2,1]$, making four cells. Thus $x<1/2$ belongs to the left half and $x\ge 1/2$ to the right half; $y<1/2$ belongs to the lower half and $y\ge 1/2$ to the upper half. This convention assigns every boundary point to exactly one cell.

The pigeonhole principle puts two of the five points in the same cell. Their differences in Cartesian coordinates have magnitude at most $1/2$, so the Pythagorean theorem gives their Euclidean distance $d$ the boundFor the plotted points $(0.1,0.1)$, $(0.4,0.4)$, $(0.8,0.2)$, $(0.2,0.8)$ and $(0.8,0.8)$, the first two occupy the lower-left cell and have Euclidean distance $\sqrt{0.3^2+0.3^2}=\sqrt{0.18}\approx 0.424264$. These Cartesian coordinates exhibit the forced pair; the argument applies to every placement of five points.

An arithmetic example. Assign eight integers to their seven residue classes modulo the integer modulus $7$. The pigeonhole principle gives two with the same residue class, so $7$ is an integer divisor of their difference. In $\{2,5,9,12,16,20,24,27\}$, for example, $2$ and $9$ satisfy the integer congruence $9\equiv 2(\mathrm{mod}7)$, and $9-2=7$. Likewise, assigning fractional parts to short intervals gives the Dirichlet approximation theorem; its existing article explains the approximation bound.

A commutative ring is Noetherian if each of its ideals has a finite generating set. Equivalently, every increasing chain of ideals eventually stops growing. For the equivalence, the union of an increasing chain is an ideal; its finitely many generators already lie in one member. Conversely, repeatedly adjoining an element outside the generated ideal would produce a nonterminating chain.

The integers are a Noetherian ring, since each ideal is principal. The Hilbert basis theorem then shows that $\mathbb{Z}[X_1,\dots ,X_n]$ is Noetherian. The infinitely generated polynomial ring $k[X_1,X_2,\dots ]$ is not: $(X_1)⊊(X_1,X_2)⊊\cdots$ never stabilizes. The condition ensures that finitely many equations suffice to describe each ideal, even when its elements form an infinite set.^[ref]

A polynomial $f\in R[X]$ over a commutative ring is a nilpotent element if $f^N=0$ for some positive integer $N$. This happens exactly when all its coefficients are nilpotent elements of $R$. For example, $2+2X$ is a nilpotent polynomial in $(\mathbb{Z}/4\mathbb{Z})[X]$, since its square is zero.

If the finitely many coefficients satisfy $a_i^{e_i}=0$, every product of more than ${\sum }_i(e_i-1)$ coefficients contains a vanishing factor, proving one direction. Conversely, reduce $f$ modulo any prime ideal: the resulting polynomial ring is an integral domain, so a nilpotent image must be zero. Each coefficient therefore belongs to every prime ideal, hence to the nilradical. In particular a polynomial ring over a reduced ring is reduced.

The minimal number of generators of a group, module, ideal, or algebraic structure is the smallest size of a generating set for the specified operations. The type of structure matters: generating a ring as an ideal, as an algebra, and as an additive group are different questions.

For a finitely generated module $M$ over a local ring $(R,\mathfrak{m})$ with residue field $k$, Nakayama's lemma gives ${\mu }_R(M)={\dim }_k(M/\mathfrak{m}M)$. Every generating set maps to a spanning set, giving the lower bound; lifts of a basis generate by Nakayama's lemma, giving equality. For example, the ideal $(x,y)$ in $k[x,y{]}_{(x,y)}$ needs two generators, since its quotient by $(x,y{)}^2$ has basis given by the classes of $x,y$.

A mathematical induction proof establishes a property $P(n)$ for every integer $n\ge n_0$ by proving its induction base case and its inductive step. If a counterexample existed, the well-ordering principle would give a least one; its predecessor and the inductive implication exclude it. The starting case excludes a counterexample at $n_0$.

The useful idea is to cover infinitely many cases with two finite pieces of reasoning. The induction base case starts the chain, and the inductive step shows that success at an arbitrary stage propagates to the next. It is especially natural when a construction adds one item at a time: another row of a diagram, another input processed by an algorithm, or another term of a sequence. The loop invariant method is the same propagation idea applied to successive stages of a computation.

For the triangular number $T_n=1+2+\cdots +n$, the proposed formula is $T_n=n(n+1)/2$. At $n=1$, both sides are one. Assuming the formula for a fixed positive integer $n$, add the next row:This is the desired formula at $n+1$, proving the inductive step. For example, $T_5=15$ and $T_6=15+6=21$; these numerical cases illustrate the general step rather than replace it.

The second picture explains where the formula comes from: two copies of the triangular arrangement tile an $n$ by $n+1$ rectangle. Thus $2T_n=n(n+1)$. The mathematical induction argument certifies how the formula continues, while the rearrangement makes its factors visible. Neither picture is restricted to the five rows drawn: both constructions are specified for every positive integer $n$.

Linearization replaces a nonlinear relation near a reference state by its first-order approximation.

A linear recurrence relation expresses each term of a sequence as a linear combination of earlier terms, possibly with an added forcing term. A constant-coefficient homogeneous recurrence of order $r$ has the formTogether with $r$ consecutive initial conditions, it determines the following terms uniquely. For example, the Fibonacci sequence satisfies $F_{n+2}=F_{n+1}+F_n$, $F_0=0$, $F_1=1$.

Substituting $u_n={\lambda }^n$ gives the characteristic polynomial of a linear recurrence. Distinct characteristic roots give independent geometric solutions; repeated roots introduce factors polynomial in $n$. This converts repeated term-by-term computation into polynomial or matrix arithmetic, useful for obtaining a distant term efficiently.

A continuously differentiable vector field on an open subset of three-dimensional Euclidean space is irrotational when its curl is zero. Under the Euclidean identification $\alpha =X_{i}d{x}^i$, this says that the differential one-form $\alpha$ is a closed differential form. The Poincaré lemma gives a potential of a conservative vector field locally. A global potential additionally requires zero line integrals around every closed curve; simply connected domains ensures this. On the punctured plane extended in the third direction, $X=(-y,x,0)/(x^2+y^2)$ has zero curl but integral $2\pi$ around a circle, so it is locally conservative and has no single-valued global potential.

An irrational number is a real number that is not a rational number: it cannot be written as $a/b$ with integers $a,b$ and $b\ne 0$. Its decimal expansion is infinite and not eventually periodic. Both $\sqrt{2}$ and $\pi$ are irrational, but their algebraic behavior differs: $\sqrt{2}$ is an algebraic number, while $\pi$ is a transcendental number.

The irrationality of the square root of two supplies a basic example: a reduced fraction $a/b$ with square two would force both $a$ and $b$ to be even. Irrational numbers are needed to describe lengths such as the diagonal of a unit square, which rational coordinates alone cannot express.

A function $f:X\to Y$ is injective if $f(x)=f(x^{\prime })$ implies $x=x^{\prime }$. Thus each element of its codomain has at most one preimage. The function $n\mapsto 2n$ from $\mathbb{Z}$ to $\mathbb{Z}$ is injective, whereas $x\mapsto x^2$ from $\mathbb{R}$ to $\mathbb{R}$ is not, since $1$ and $-1$ have the same image.

The choice of domain of a function matters: restricting $x\mapsto x^2$ to the nonnegative real numbers makes it injective. A function is bijective exactly when it is both injective and surjective; injectivity alone does not require reaching every element of the codomain.

For functions $f:X\to Y$ and $g:Y\to Z$, their function composition is $g\circ f:X\to Z$, defined by $(g\circ f)(x)=g(f(x))$. The rightmost function is applied first. Matching the intermediate codomain and domain of a function makes the expression well-defined.

For self-maps of the real numbers, take $f(x)=x+1$ and $g(x)=2x$. Then $(g\circ f)(x)=2x+2$, whereas $(f\circ g)(x)=2x+1$. Thus function composition need not be commutative. It does have the associative property: both $(h\circ g)\circ f$ and $h\circ (g\circ f)$ evaluate to $h(g(f(x)))$ whenever each intermediate codomain matches the next domain of a function. The identity function leaves composition unchanged, making self-maps particularly useful as a monoid of transformations.