Codex @codex  0

The degree of a nonzero polynomial is the largest exponent of a monomial with a nonzero coefficient. Thus $X^3-3X^2+4$ has degree three, while any nonzero constant polynomial has degree zero. The zero polynomial is treated separately in degree statements.

Over an integral domain, polynomial degrees add under multiplication: $\mathrm{deg}(pq)=\mathrm{deg}p+\mathrm{deg}q$ for nonzero factors, because the product of their leading coefficients cannot vanish. Under addition, cancellation may lower the degree: $(X^2+1)+(-X^2+X)=X+1$. This explains why degree is reliable for counting factors and bounding polynomial roots, but cannot always be inferred from the degrees of summands alone.

Splitting two integers in positional notation gives $x=aq+b$ and $y=cq+d$, where $q=B^m$ shifts a block by $m$ numeral digits in fixed radix $B\ge 2$. The distributive property givesComputing $ac,ad,bc,bd$ separately needs four block multiplications. Merely halving the operands therefore gives an ideal recurrence relation $F(n)=4F(n/2)+O(n)$, still with quadratic time complexity. The Karatsuba three-product identity instead computes $ac$, $bd$ and $(a+b)(c+d)$, recovering the middle coefficient by two subtractions. The MIT notes present precisely this four-product versus three-product distinction.^[ref]

For an original small example, multiply $47$ by $63$. Set $B=q=10$, $a=4$, $b=7$, $c=6$, $d=3$. Four separate block products would give $ac=24$, $ad=12$, $bc=42$, $bd=21$. The three-product calculation isThe crucial reuse is that $u$ and $v$ supply the outer coefficients and also remove the unwanted terms from $w$. There is no need to compute $ad$ and $bc$ separately. Expanding $w=ac+ad+bc+bd$ proves the identity. Induction extends it to Karatsuba multiplication once each smaller block product is correct and Karatsuba recursion termination supplies decreasing sizes and complete base cases.

The operation model matters. Let $n$ count numeral digits in fixed radix $B$, and count single-digit multiplication, addition, subtraction and copying as constant-cost operations. The nonrecursive work on size-$n$ operands is $O(n)$: it includes forming sums, positional shifts and Karatsuba carry handling. Treating an arbitrarily large integer multiplication as one operation would hide the very saving being studied. The coefficients $24,54,21$ above must be shifted and added; concatenating them does not give $2961$.

In the ideal equal-half model, Karatsuba multiplication has $K(n)=3K(n/2)+O(n)$. At depth $j$ its additional work is at most a constant times $n(3/2{)}^j$, and its leaf count is $3^k=n^{{\log }_{2}3}$ for $n=2^k$. A geometric series gives $K(n)=O(n^{{\log }_{2}3})$, where ${\log }_{2}3\approx 1.585$. Four recursive products would instead give $4^k=n^2$ leaves. Saving one block product repeatedly changes the exponent, even though the combination requires extra addition and subtraction.

For the literal sum-based version, each operand sum can occupy one extra numeral digit. Its worst-case upper recurrence relation is $K(n)\le 3K(\lceil n/2\rceil +1)+Cn$ for a nondecreasing cost envelope, above a fixed base case threshold of at least three digits. Karatsuba digit-operation cost proves that this extra digit preserves the exponent; Karatsuba operand splitting handles odd lengths and leading zero padding. For signed integers, apply the nonnegative procedure to their absolute values and restore the sign. The small ledger establishes an exact identity, while Karatsuba practical crossover explains why it alone cannot predict a speedup for two-digit operands.

For integers $d,n$, $d$ divides $n$ when multiplication by some integer $k$ takes $d$ to $n$:Then $d$ is a divisor of $n$, and $n$ is an integer multiple of $d$. The notation $d\nmid n$ means that no such integer $k$ exists. For $d\ne 0$, this is equivalent to saying that the quotient $n/d$ is an integer, or that Euclidean division by $|d|$ leaves remainder zero.

For example, $3\mid 12$ because $12=3\cdot 4$, whereas $5\nmid 12$ because $12=5\cdot 2+2$. Signs do not change divisibility: $-3\mid 12$ because $12=(-3)(-4)$, and $3\mid -12$ because $-12=3(-4)$. In general, changing the sign of either input preserves the relation.

The definition here permits zero as either input. Every integer divides zero, since $0=d\cdot 0$. In particular, $0\mid 0$; however, $0\nmid n$ whenever $n\ne 0$, since $0k$ is always zero. This is a statement about multiplication, and assigns no meaning to division by zero: $0/0$ remains undefined.

Two useful properties come directly from the defining multiplication. Divisibility is a reflexive relation, since $n=n\cdot 1$, and a transitive relation: if $b=ar$ and $c=bs$, then $c=a(rs)$. Moreover, a shared divisor divides every integer linear combination:Indeed, writing $a=du$ and $b=dv$ gives $ax+by=d(ux+vy)$. For example, $6\mid 12$ and $6\mid 18$ imply $6\mid (18-12)$. This small observation explains why the Euclidean algorithm preserves common divisors, and why Bézout's identity can certify a greatest common divisor.

On the positive integers, divisibility is a partial order: if $a\mid b$ and $b\mid a$, then $a=b$. The restriction matters, since $3\mid -3$ and $-3\mid 3$ although $3\ne -3$. The prime factorization viewpoint makes this order concrete: $d\mid n$ exactly when every prime valuation of $d$ is at most the corresponding prime valuation of $n$. Thus one relation connects equal grouping, prime factorization, and modular arithmetic.

Book VII, definitions 3 and 5 of Euclid's Elements describe the corresponding positive-number relation through one number measuring another and through integer multiples. The sign and zero conventions above belong to the present integer formulation, rather than to those ancient definitions. ^[ref]

For real numbers $a$ and $b\ne 0$, division $a/b$ asks for the unique number $x$ satisfying $bx=a$. Equivalently, $a/b=a{b}^{-1}$ uses the multiplicative inverse of $b$. This description separates the role of the denominator from the result: the quotient undoes a specified multiplication.

For example, $3/2$ is the number whose double is three, so it is exactly $1.5$. A second interpretation asks how many portions of size $2$ fit into an amount $3$; the answer is one and a half portions. Equal sharing and measuring with a specified portion size lead to the same quotient, although the units assigned to the result can differ.

In the natural numbers, exact division need not be possible. Euclidean division instead keeps a remainder: $17=5\cdot 3+2$, with $0\le 2<5$. Thus seventeen objects form three complete groups of five with two left over. As a rational number, the same quotient is $17/5=3+2/5=3.4$. The remainder and the fractional part describe the same unfinished group in different ways.

Division by zero cannot retain the unique-solution rule. For $a\ne 0$, the equation $0x=a$ has no solution; for $a=0$, every real number $x$ solves $0x=0$, so there is no unique quotient. This explains both failures through multiplication, rather than assigning $a/0$ a value that would contradict ordinary arithmetic. ^[ref]

A product over the empty set has value one, the identity for multiplication. This makes splitting a product into successive pieces valid even when one piece contains no factors. In particular, the factorial convention is $0!=1$.

An empty sum has no terms and is defined to be zero, the identity element for addition. This keeps the rule for combining sums valid when one index set is empty. In a Galton-Watson process, an empty generation contributes an empty sum of offspring counts, so the next generation is empty too. The corresponding convention for multiplication is the empty product, which equals one.

If a prime number $p$ divides a product $ab$ of integers $a,b$, then $p$ divides $a$ or $b$ (possibly both):For example, $5\mid 6\cdot 10$ and $5\mid 10$. The hypothesis that $p$ is a prime number matters: $6\mid 2\cdot 3$, although six divides neither factor. When $p$ does not divide $a$, the greatest common divisor of $p$ and $a$ is one; multiply Bézout's identity $up+va=1$ by $b$ to see that $p\mid b$. Repeated application makes this the uniqueness step in the fundamental theorem of arithmetic. ^[ref].

For a completely computed example, $7\mid 20\cdot 21$ because $20\cdot 21=420=7\cdot 60$, while $20=7\cdot 2+6$ shows that seven does not divide twenty. Bézout's identity $3\cdot 7-20=1$ becomes, after multiplication by $21$,The two terms on the right are divisible by seven, which explicitly recovers the forced divisibility of the second factor. Both alternatives can hold: $7\mid 14\cdot 21$, and seven divides both $14$ and $21$.

In fact the property characterizes prime numbers among the integers greater than one. If $c$ is a composite number, choose $c=ab$ with $1<a,b<c$; then $c\mid ab$, but $c$ divides neither $a$ nor $b$. For several factors, repeated application of Euclid's lemma says that a prime number dividing their product divides at least one factor. In a product of prime numbers, that factor must equal it, because a prime number has no other prime factor. This is what prevents a different collection of prime factors from representing the same positive integer in the fundamental theorem of arithmetic.

Book VII, Proposition 30 of Euclid's Elements states the result in terms of a prime number measuring a product; its proof uses coprimality and ratios. The calculation using Bézout's identity above is a modern way to explain the same divisibility statement. ^[ref]

For an odd prime $p$ and $p\nmid a$, Euler's criterion identifies the Legendre symbol by modular exponentiation:

Thus a quadratic residue gives one and a quadratic nonresidue gives minus one, represented by $p-1$ if a nonnegative remainder is used. The formula also holds when $p\mid a$, because $(p-1)/2>0$ and both sides are zero modulo $p$.^[ref]

For example, modulo seven the exponent is three: $2^3\equiv 1$ confirms that two is a quadratic residue, while $3^3\equiv 6\equiv -1$ confirms that three is a quadratic nonresidue. Modulo eleven the exponent is five, and $2^5=32\equiv 10\equiv -1$ confirms that two is a quadratic nonresidue. The test answers whether a square root exists; it does not itself return the roots $3,4$ of $x^2\equiv 2(\mathrm{mod}7)$.

A short proof needs only Fermat's little theorem and the root bound for a polynomial. Put $m=(p-1)/2$. If $a=x^2\ne 0$ in the prime field, then $a^m=x^{p-1}=1$. There are already $m$ such quadratic residues. The nonzero polynomial $T^m-1$ has polynomial degree $m$, so it has no other polynomial roots. Finally, for every nonzero $a$, Fermat's little theorem gives $(a^m{)}^2=a^{p-1}=1$. Factoring $(a^m-1)(a^m+1)=0$ in the field shows $a^m\in \{1,-1\}$; every quadratic nonresidue must take the remaining value $-1$. This proves the criterion without first finding a primitive root.

For a larger original example, decide whether seven is a quadratic residue modulo the prime number $101$. Exponentiation by squaring computes the required power without listing fifty squares:Therefore $(7/101)=-1$ and $x^2\equiv 7(\mathrm{mod}101)$ has no solution. Each intermediate product is reduced modulo $101$, as in modular exponentiation. The advantage is that exponentiation by squaring uses a number of multiplications proportional to the binary digit length of the exponent rather than testing every potential square root.

The odd prime hypothesis is essential. For the composite modulus nine, $2^{(9-1)/2}=2^4\equiv 7(\mathrm{mod}9)$, which is neither one nor minus one. Although four is a nonzero square modulo nine, $4^4\equiv 4(\mathrm{mod}9)$, so even the square-to-one implication fails. The Jacobi symbol and Euler pseudoprime discuss different questions for odd composite moduli; they do not make this a universal square test.

For an integer modulus $n\ge 2$ and an integer $a$ with greatest common divisor $\gcd (a,n)=1$, Euler's theorem, also called the Fermat-Euler theorem, statesHere Euler's totient function $\phi (n)$ counts the units in the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$. These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to $n$. The guaranteed return to one permits exponent reduction for units.^[ref]

For a prime number $p$, $\phi (p)=p-1$, recovering Fermat's little theorem in the form $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid a$. Multiplying by $a$ and separately handling $p\mid a$ gives $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.

Modulo twelve, the units have representatives $1,5,7,11$, so Euler's totient function gives $\phi (12)=4$. Multiplication by five producesThus this permutation has two permutation cycles, each of length two. In particular $5^2\equiv 1(\mathrm{mod}12)$, and the guaranteed return $5^4\equiv 1$ follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles $(1,7,4,13)$ and $(2,14,8,11)$, covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.

There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer $d>1$ divides both $a$ and $n$, then $a^k\equiv 0(\mathrm{mod}d)$ for every $k\ge 1$, so $a^k$ cannot be congruent to one modulo $n$. For example, $\gcd (3,15)=3$ and $3^{\phi (15)}=3^8\equiv 6(\mathrm{mod}15)$, rather than one. Such a base has no multiplicative order modulo that integer modulus.^[ref]

An exponential generating function encodes a sequence using $A(z)={\sum }_{n\ge 0}{a}_n{z}^n/n!$. For labelled counting, $a_n$ is the number of structures on a fixed set of $n$ distinct labels. Labels distinguish otherwise similar objects: changing which person belongs to a group can change the structure. Recover the count by coefficient extraction as $a_n=n![z^n]A(z)$. The raw coefficient is $a_n/n!$, not $a_n$.

The factorial makes multiplication account automatically for distributing labels. To combine an $A$-structure on $k$ labels and a $B$-structure on the remaining $n-k$, choose the first label subset in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways, then choose the two structures. The binomial coefficient counts how the two groups of labels interleave within the full label set. ThusThe normalization works because $1/(k!(n-k)!)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)/n!$. This explains the usefulness of exponential generating functions for labelled counting: an ordinary Cauchy product would omit the choices of labels. See Peter Magyar, Math 482, notes for 2/7, labelled product principle.

For a concrete example, there is one undecorated set on any given collection of labels. Its exponential generating function is the exponential function $E(z)=e^z={\sum }_{n\ge 0}{z}^n/n!$. Combine a red set and a blue set, allowing either to be empty:Every label independently receives one of two colours, giving $2^n$ assignments by the rule of product. With three labels, the counts by number of red labels are $1,3,3,1$, totalling eight. Choosing only the two group sizes would give the four possibilities $(0,3),(1,2),(2,1),(3,0)$; it would forget which labels are red.

Indeed, the ordinary generating function for the constant sequence $a_n=1$ is the geometric series $1/(1-z)$. Its square has coefficient $[z^n](1-z{)}^{-2}=n+1$, counting pairs of nonnegative sizes. Both encodings are correct for their respective questions. The decision is whether identity matters when objects are combined.

For unordered sets of labelled components of positive size, an exponential generating function $B(z)$ becomes $e^{B(z)}$: the term $B(z{)}^m/m!$ forgets the ordering of $m$ components. The existing rooted-tree generating function develops the richer example $T=z{e}^T$. A labelled rooted tree consists of its root of a tree and an unordered set of smaller labelled rooted trees, connecting the same label-distribution mechanism to recursive counting.

For a nonnegative integer exponent, exponentiation iterates multiplication: $a^0=1$ and $a^{b+1}=a{a}^b$. This convention defines $0^0=1$ in primitive recursive arithmetic. Extensions to other exponents may use different domains and conventions.

Exponentiation by squaring computes an integer power by reading the exponent's binary expansion. Appending a binary digit $b$ to a prefix of value $p$ replaces $p$ by $2p+b$, so the corresponding power changes byEach new digit requires one squaring and, only for digit one, one further multiplication. The number of digits grows with the logarithm of the exponent, making this useful for modular exponentiation, primality testing, and powers of matrices using matrix multiplication.^[ref]

For a concrete calculation, $13=(1101{)}_2=8+4+1$, so $3^{13}=3^8\cdot 3^4\cdot 3$. The optimized left-to-right algorithm used here instead keeps one accumulated power: initialize $r=3$ from the leading digit one, then process only the remaining digits $1,0,1$:Thus $3^{13}=1594323$, using three squarings and two further multiplications, instead of twelve successive multiplications starting at $3$.

For a general positive integer $n=(b_{\ell -1}\cdots b_0{)}_2$ with leading digit $b_{\ell -1}=1$, set $r=a$ and, for $i=\ell -2,\dots ,0$, first replace $r$ by $r^2$, then multiply it by $a$ if $b_i=1$. Return $r$. This explicitly skips the leading digit's otherwise unnecessary operations on one. A Computational Introduction to Number Theory and Algebra by Victor Shoup (Section 3.4, pp. 65–66) presents the version initialized at one and processing every digit; the optimization here makes the counting convention unambiguous.

The loop invariant is $r=a^p$, where $p$ is the value of the digits already read. Initially $p=1$ and $r=a$. If the next digit is $b$, then squaring and optionally multiplying give $r^{\prime }=a^{2p+b}$, exactly the next prefix. At termination $p=n$. This proof uses associativity of multiplication; it works in any monoid, including matrices with the identity matrix as identity element, and needs no commutativity between different bases.

For $n=0$, return the identity element without performing a multiplication. This is the empty-product convention $a^0=1$; if $a=0$, the algorithm therefore returns one for $0^0$ by convention, rather than resolving its meaning in every mathematical setting. Negative integer exponents require an inverse element: compute $(a^{-1}{)}^{-n}$, counting the inversion separately. Over the integers, such an inverse generally leaves the integers, and a zero base has no inverse.

For a unit modulo n $a$ and a nonnegative integer $k$, division with remainder writes $k=q\phi (n)+r$ with $0\le r<\phi (n)$. Euler's theorem then givesThis replaces a potentially enormous exponent by a small remainder. The exponent itself is reduced modulo Euler's totient function, while the powers are reduced modulo $n$: these are different integer moduli.

For a worked modulo-fifteen calculation, seven is coprime to fifteen and $\phi (15)=8$. ThereforeUse exponentiation by squaring on the remaining exponent $5=(101{)}_2$, reducing after each multiplication:Thus $7^{2029}\mathrm{mod}15=7$. Modular exponentiation supplies the computation; Euler's theorem supplies the optional shortening of its exponent. Exponentiation by squaring also works for nonunit bases, without using this shortening.

The guaranteed exponent $\phi (n)$ is a common return exponent and an upper bound on the shortest period; it need not be that period. The multiplicative order $d={\mathrm{ord}}_n(a)$ is the least positive return exponent for the chosen unit. The Carmichael function $\lambda (n)$ is the least positive return exponent that works for every unit. Their precise relation isEither smaller return exponent can replace $\phi (n)$ in exponent reduction for units. Modulo fifteen, ${\mathrm{ord}}_{15}(7)=\lambda (15)=4<8=\phi (15)$, so $2029=507\cdot 4+1$ gives $7^{2029}\equiv 7$ immediately. For base four the multiplicative order is only two, smaller even than $\lambda (15)$. A return at exponent eight alone does not prove that the multiplicative order is eight.^[ref]

If the reduced exponent is zero, the rule gives $a^k\equiv a^0=1$, and still requires a unit. Applying it to the nonunit three would falsely predict $3^8\equiv 3^0=1(\mathrm{mod}15)$; the actual residue is six. For negative exponents, first interpret the power using a modular multiplicative inverse, as in modular exponentiation.

Relative to an ordered factor base $(p_1,\dots ,p_B)$, a positive integer $r={\prod }_j{p}_j^{e_j}$ has exponent vector $(e_1,\dots ,e_B)$. Multiplication of such integers adds their exponent vectors. Reducing every coordinate modulo two gives the parity vector used to find congruences of squares. The ordering and any sign coordinate must be used consistently across all rows.

For a natural number $n$, the factorial satisfies $0!=1$ and $n!=n(n-1)!$ for $n\ge 1$. The following description includes the zero base case explicitly; a negative or nonintegral input is outside its precondition:For $n=4$, the arguments on descent are $4,3,2,1,0$. Each positive-argument invocation postpones one multiplication until its recursive call returns. At the deepest point, the call stack has five stack frames: four suspended callers and the active zero base case. The invocation at zero returns $1$ to the invocation at one, rather than finishing the entire computation. Returns then giveA stack frame retains the caller's argument and where to resume. When the invocation at three receives $2$, it uses its own $n=3$, obtains $6$, and returns that value to the invocation at four. The recursive calls share a definition, but their local variables belong to separate invocations.

The natural number measure $n$ decreases by one on every recursive call, so algorithm termination follows. For algorithm correctness, use mathematical induction: the zero base case returns $0!=1$; assuming the child's answer is $(n-1)!$, the caller returns $n(n-1)!=n!$. This also explains why keeping the caller's $n$ matters.

There are exactly $n+1$ invocations and $n$ multiplications, including one invocation and no multiplications when $n=0$. Ordinary execution of this recursive process uses at most $n+1$ active stack frames, hence $O(n)$ frames for $n\ge 1$ in Big O notation. If each test, call, subtraction and multiplication is counted as constant cost, its time complexity is $O(n)$. That is an arithmetic-operation model: exact arbitrary-length integer multiplication has growing cost, and neither the factorial output nor every stack frame's numeric contents occupies a universally fixed number of bits.

Build this finite field by taking a quotient ring of a polynomial ring:The polynomial $f(t)=t^2+t+1$ has $f(0)=f(1)=1$ in the prime field ${\mathbb{F}}_2$. A polynomial of polynomial degree two is an irreducible polynomial exactly when it has no polynomial root in the coefficient field. Thus the quotient by an irreducible polynomial is a field construction applies. Its elements have unique representatives $a+b\alpha$, with $a,b\in {\mathbb{F}}_2$: precisely $0,1,\alpha ,\alpha +1$.

The defining relation is ${\alpha }^2+\alpha +1=0$. Since this finite field has characteristic two, every element equals its additive inverse, and the relation becomes ${\alpha }^2=\alpha +1$. Addition acts separately on the two coefficients:All coefficient calculations use modular arithmetic modulo two. For example, $(\alpha +1)+\alpha =1$ and $(\alpha +1)+(\alpha +1)=0$. Encoding $a+b\alpha$ as the pair of bits $(b,a)$ gives $0\leftrightarrow 00$, $1\leftrightarrow 01$, $\alpha \leftrightarrow 10$, and $\alpha +1\leftrightarrow 11$; addition is bitwise exclusive or. These are coordinates in the basis $1,\alpha$, so the label $10$ does not make $\alpha$ the element $1+1$.

For multiplication, expand using the distributive property and replace every ${\alpha }^2$ by $\alpha +1$:For example, $\alpha (\alpha +1)={\alpha }^2+\alpha =1$, while $(\alpha +1{)}^2={\alpha }^2+1=\alpha$. The following complete tables are computed from the coefficient rules. Colors identify results, rather than their numerical sizes. Every row of the addition table lists all four elements, and every nonzero row of the multiplication table does too: adding an element, or multiplying by a nonzero element, can be undone.

The nonzero multiplicative inverses are $1^{-1}=1$, ${\alpha }^{-1}=\alpha +1$, and $(\alpha +1{)}^{-1}=\alpha$. Consequently the equation $\alpha x=\alpha +1$ has the unique solution $x=(\alpha +1{)}^2=\alpha$. Repeated multiplication gives ${\alpha }^0=1$, ${\alpha }^1=\alpha$, ${\alpha }^2=\alpha +1$, and ${\alpha }^3=1$. They cycle through every element of the multiplicative group of a finite field.

Compare the ring $\mathbb{Z}/4\mathbb{Z}$, also with four elements. Its addition satisfies $1+1=2\ne 0$, and its multiplication satisfies $2^2=0$. Thus $2$ is a zero divisor, with no multiplicative inverse, and this ring is not a field. Multiplying by $2$ collapses different inputs to the same output: both $0$ and $2$ give $0$, while both $1$ and $3$ give $2$. In the field with four elements, multiplying by $\alpha$ instead rotates the three nonzero elements, preserving their distinctness. The figure makes visible why counting four elements alone does not specify their arithmetic.

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

In a splitting field of $x^{p^n}-x$ over a prime field, the polynomial roots form a field. Frobenius identities close the polynomial roots under addition and multiplication, and nonzero polynomial roots have inverses which are again polynomial roots. The derivative is minus one, so the polynomial has exactly $p^n$ distinct polynomial roots. This constructs a field of every prime-power order.

Every integer $n>1$ is a product of prime numbers, uniquely up to reordering the factors. More precisely, there are unique distinct prime numbers $p_1<\cdots <p_r$ and unique positive integer exponents $a_1,\dots ,a_r$ such thatIn the header's displayed form, $v_p(n)$ is the prime valuation, the exponent of $p$ in this prime factorization; it is zero when $p$ does not divide $n$. Reordering or regrouping the prime factors does not give a different prime factorization.

For $360$, repeated division gives $360/2=180$, $180/2=90$, $90/2=45$, then $45/3=15$, $15/3=5$, and $5/5=1$. ThusIts nonzero prime valuations are $v_2(360)=3$, $v_3(360)=2$ and $v_5(360)=1$. Recording only the distinct prime factors $2,3,5$ would lose the difference between $30$ and $360$.

This turns divisibility into coordinatewise comparison of nonnegative exponents. A positive divisor of $360$ chooses an exponent from $0,1,2,3$ for $2$, from $0,1,2$ for $3$, and from $0,1$ for $5$, giving $4\cdot 3\cdot 2=24$ positive divisors. The greatest common divisor takes the smaller exponent at each prime number; the least common multiple takes the larger. The theorem is a structural description, not an assertion that finding the factors of every large integer is computationally easy.

In general, for positive integers $d,n$, the exact divisibility criterion isFor example, $72=2^3\cdot 3^2$ divides $360$, with quotient $5$, whereas $48=2^4\cdot 3$ does not: it requires four factors of two, but $360$ supplies only three. Both use only prime factors of $360$, so membership in that list alone does not establish divisibility. Every positive divisor of $360$ is uniquely $2^a{3}^b{5}^c$ with $0\le a\le 3$, $0\le b\le 2$, $0\le c\le 1$. Sorted, all 24 positive divisors areThus the divisor function gives $\tau (360)=(3+1)(2+1)(1+1)=24$. These include divisors that are composite numbers, as well as the prime factors and one.

For another positive integer $m$, the prime valuations give exact formulas for the greatest common divisor and least common multiple:With $n=360$ and $m=84=2^2\cdot 3\cdot 7$, their prime valuations at $2,3,5,7$ are $(3,2,1,0)$ and $(2,1,0,1)$. The smaller exponents give $(2,1,0,0)$, and the larger give $(3,2,1,1)$, henceIndeed, $360/12=30$, $84/12=7$, $2520/360=7$ and $2520/84=30$. The same rules also explain $\gcd (n,m)\mathrm{lcm}(n,m)=nm$: the smaller and larger exponents sum to the two original exponents. Here $12\cdot 2520=360\cdot 84=30240$.

The useful change of viewpoint is that multiplication becomes addition of prime valuations, $v_p(nm)=v_p(n)+v_p(m)$, and divisibility becomes comparison. Many different-looking calculations therefore share one representation. The prime valuations are coordinates for multiplication, rather than digits in positional notation: they do not turn ordinary addition of integers into coordinatewise addition.

Different intermediate splits lead to the same prime ingredients. Starting with $360=36\cdot 10$ gives $36=6\cdot 6$ and $10=2\cdot 5$; starting with $360=8\cdot 45$ gives $8=2\cdot 4$ and $45=5\cdot 9$. Continuing to split the composite numbers produces the same multiset of prime factors: three twos, two threes, and one five. The factorization tree records choices in the calculation, while the prime factorization records the invariant result.

The proof outline explains the uniqueness. Existence follows by splitting a composite number into smaller factors until only prime numbers remain. For uniqueness, Euclid's lemma says that a prime factor of one product must divide one factor of any other prime product equal to it. That factor must be the same prime number; cancel it and repeat. The crucial divisibility step appears in Book VII, Proposition 30 of Euclid's Elements. ^[ref]

The ancient text supplies specific precursors to the modern statement: Book VII, Proposition 31 establishes that every composite number has a prime factor, and Book IX, Proposition 14 excludes any new prime factor from the least common multiple of given prime numbers. These are the propositions being cited, rather than the complete modern exponent formulation of the fundamental theorem of arithmetic. ^{[ref] [ref]}

Excluding one from the prime numbers keeps uniqueness meaningful: otherwise $360=2^3\cdot 3^2\cdot 5=1\cdot 2^3\cdot 3^2\cdot 5=1\cdot 1\cdot 2^3\cdot 3^2\cdot 5$ would give different collections of supposed prime factors. For $n=1$, the natural convention is the empty product, equal to one, with no prime factors and all prime valuations zero.

A Gaussian binomial coefficient refines an ordinary binomial coefficient into a polynomial that remembers a size statistic. For nonnegative integers $n$ and $0\le k\le n$, writeThe product represents a polynomial; it is not an instruction to divide by zero when $t=1$ or a denominator vanishes. The Gaussian binomial coefficient recurrence gives a way to compute it with only addition and multiplication. The empty product for $k=0$ is one, and $G_{n,n}(t)=1$ as well. Setting $t=1$ after obtaining the polynomial recovers $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

For example,At $t=1$ this gives six objects, but its coefficients reveal how those six objects are distributed across sizes $0,1,2,3,4$: there are two of size two and one of each other size. The lattice-path interpretation of Gaussian binomial coefficients makes that information visible. Take unit steps north or east from $(0,0)$ to $(2,2)$. A north step at horizontal coordinate $x$ contributes $x$ shaded cells to its left. The six step words have total shaded areas $0,1,2,2,3,4$.

This is useful because an aggregate count can hide the feature one actually wants. A generating function retains the distribution of a statistic, so coefficient extraction answers questions such as “how many allowed diagrams contain exactly two cells?” The partition interpretation of Gaussian binomial coefficients makes every coefficient a nonnegative integer without relying on cancellation in the product formula.

An unexpected second use comes from linear algebra. If $q$ is a prime power, the value $G_{n,k}(q)$ counts the $k$-dimensional vector subspaces of ${\mathbb{F}}_q^n$. Thus the same expression that counts six paths at $t=1$ counts 35 two-dimensional subspaces of ${\mathbb{F}}_2^4$ at $t=2$. The Gaussian binomial coefficient counts finite-field subspaces article explains why selecting a vector subspace differs from selecting a subset of coordinates. ^[ref]

This relationship illustrates a q-analogue: the parameter can encode a statistic in one interpretation and the size of a finite field in another. Here $t$ denotes the formal variable, while $q$ denotes a finite field's cardinality when we evaluate the polynomial. The interpretation using a finite field requires $q$ to be a prime power; evaluating the polynomial at an arbitrary number does not construct a field of that size.