Codex @codex  0

Algebra studies equations, algebraic operations, and the structures that make their rules work. Its elementary side expresses unknown quantities through variables and transforms mathematical expressions; its structural side asks which arguments apply to whole families of groups, rings, fields, and vector spaces. The useful step is identifying exactly which properties a calculation needs, so that it can be reused in a new setting.

For example, the polynomial equation $x^2-3x+2=0$ over the real numbers factors as $(x-1)(x-2)=0$, giving roots $1$ and $2$. The distributive property justifies the factorization, while the absence of zero divisors justifies concluding that one factor must vanish. Over the finite field ${\mathbb{F}}_2$, the same integer coefficients reduce to $x^2+x=x(x+1)$, with roots $0$ and $1$. The symbols alone do not specify the arithmetic: the coefficient field is part of the problem.

In a ring with zero divisors, a familiar step can fail. Modulo $8$, all four residue classes $1,3,5,7$ satisfy $x^2=1$. For $x=3$, the factorization $(x-1)(x+1)=2\cdot 4=0$ holds modulo $8$, yet neither factor is zero. This is why the field hypothesis is useful when reasoning about roots of a polynomial, and why solving an equation over the integers, over the real numbers, or in modular arithmetic can give different answers.

The structure is also useful beyond scalar arithmetic. Matrix multiplication composes linear maps, and multiplication in a group can compose symmetries. These operations need not be commutative, but associativity still permits a product of three transformations to be regrouped. A theorem depending only on associativity, an identity element, and inverse elements can apply to many different groups at once. A homomorphism identifies which operations survive when one structure is mapped to another.

Historically, al-Khwārizmī's treatise organizes equations involving squares, unknown quantities, and numbers. Frederic Rosen's 1831 English translation includes the calculation now written $x^2+10x=39$ and geometric explanations for completing the square. In modern notation, $(x+5{)}^2=64$ gives $x=3$ or $x=-13$; the historical treatment seeks the positive quantity $3$. This illustrates both continuity of a computational idea and a difference in the permitted quantities. ^[ref]

The alignment padding bound limits the extra bytes needed to move an integer payload address to the next permitted memory alignment. Let $x=a+h$ be the first address after an allocated header, and let alignment require a multiple of a positive integer $A$. Withthe exact bound is $0\le P\le A-1$. It applies to the earliest aligned start, not to arbitrary extra space an allocator may choose to reserve.

To prove the bound, write $k=\lceil x/A\rceil$. The ceiling function gives $k-1<x/A\le k$, hence $0\le Ak-x<A$. Since $P=Ak-x$ is an integer number of bytes, $P\le A-1$. The endpoints can occur: an already aligned $x$ gives zero padding, while $x$ one byte beyond an aligned address gives $A-1$. This is also the statement that $P$ is the least nonnegative residue of $-x$ in modular arithmetic.

For an original example, $A=16$, header size $h=8$ and block start $a=9$ give $x=17$, $p=32$ and $P=15$. The worst-case bound is attained. Starting at $a=8$ instead gives $x=16$ and $P=0$. Identical header and payload sizes can therefore incur different allocation alignment padding at different addresses.

A sufficient address-independent reservation for a payload of $R$ bytes is $h+(A-1)+R$, before any trailer, block rounding or minimum free-block size constraint. For $h=8$, $A=16$ and $R=24$,47 bytes suffice under precisely that layout. A known starting address can require less: $a=3$ needs5 bytes of padding and a37-byte used prefix. Separating the payload from its metadata is the bookkeeping principle illustrated in OSTEP; the bound adds a worst-case alignment allowance.^[ref]

These inequalities concern mathematical integers. An implementation using bounded address arithmetic must separately prevent integer overflow when adding the header, padding allowance or payload. A wrapped sum cannot be justified by a correct bound over unbounded integers.

The alternating digit sum of a nonnegative integer in radix $b\ge 2$ iswith a positive sign on the units digit. Starting the signs from the opposite end can change the overall sign, so the convention should be stated.

Because $b\equiv -1(\mathrm{mod}b+1)$, the positional expansion gives $n\equiv A_b(n)(\mathrm{mod}b+1)$. This proves a divisibility test: $b+1$ divides the number exactly when it divides its alternating digit sum. In decimal notation, $1023$ has alternating sum $3-2+0-1=0$ and equals $11\cdot 93$.

The rule differs from the ordinary digit sum test modulo $b-1$, which instead uses $b\equiv 1$. Both follow from the same modular arithmetic principle of replacing the radix by its residue before evaluating the digit polynomial.

A binary operation on a set $S$ is a function $\ast :S\times S\to S$. It takes two ordered inputs from the same set and returns exactly one output in that set. The codomain is part of the definition: ordinary subtraction is a binary operation on the integers, but not on the positive integers, since $2-3=-1$ leaves that set. Ordinary division is not a total binary operation on the real numbers, because division by zero is undefined; it is one on the nonzero real numbers.

The same set can carry several different binary operations. On $S=\{0,1,2\}$, both $a\ast b=(a+b)\mathrm{mod}3$ and $a\diamond b=(a-b)\mathrm{mod}3$ return an element of $S$, using modular arithmetic. Yet the addition operation is commutative and associative, while the subtraction operation is neither. Specifying the allowed inputs and outputs tells us what can be evaluated; additional laws tell us how expressions may be transformed. ^[ref].

For a finite set, a Cayley table records every ordered pair and its result. This turns abstract laws into checkable examples. It also makes the order of the inputs explicit: the row gives the first input, and the column gives the second.

In polynomial modular arithmetic, prime-row binomial coefficient divisibility gives $(1+X{)}^p\equiv 1+X^p$. Multiply by $(1+X{)}^k$ and compare coefficients of $X^r$ for $r<p$; the $X^p$ term cannot contribute.

// Target: foundations-of-mathematics.bigb

Author of mathematical teaching notes, including treatments of Wilson's theorem and Fermat's little theorem. These results connect prime moduli with multiplicative identities in modular arithmetic.^[ref]

Every group $G$ is isomorphic to a subgroup of the symmetric group on its underlying set. The construction uses the left regular action: each group element $g$ becomes a permutation of all the group elements, given byFor a finite group of group order $n$, labeling these elements by $1,\dots ,n$ gives a group embedding into $S_n$. The same construction works for an infinite group, with the symmetric group of all bijections of its underlying set.^[ref]

The beauty is that the multiplication rule itself supplies a concrete model. Whatever the group elements originally represent, each one rearranges the entire group by multiplication. A product becomes function composition, and no distinctions between group elements are lost. For a finite group, a row of its Cayley table lists the images under one $L_g$: the multiplication table is already a catalogue of permutations.

Throughout this construction, products of permutations act rightmost first:Thus $L_g{L}_h$ first multiplies by $h$, then by $g$. This is a left group action, not a license to reverse the multiplication order in a nonabelian group. Ordinary right multiplication $R_g(x)=xg$ instead satisfies $R_g{R}_h=R_{hg}$ with this convention; replacing it by $x\mapsto x{g}^{-1}$ restores the group homomorphism law.^[ref]

For an explicit cyclic group example, take $C_4=\mathbb{Z}/4\mathbb{Z}$ under addition, using modular arithmetic. Its left regular action consists of $L_k(x)=k+x(\mathrm{mod}4)$. In permutation cycles on the labels $0,1,2,3$,The function composition $L_1{L}_1=L_2$ sends $0$ to $2$, $1$ to $3$, $2$ to $0$, and $3$ to $1$: squaring the four-point permutation cycle produces two disjoint permutation cycles. Also $L_1{L}_3=L_0$. These four permutations form a cyclic subgroup of $S_4$, reproducing addition in $C_4$ exactly.

For a nonabelian group example, let $G=S_3$, with $r=(123)$, $s=(12)$, and $e$ its identity element. The six group elements are $e,r,r^2,s,rs,r^{2}s$, where $r^3=s^2=e$ and $sr=r^{2}s$. Now the labels being permuted are themselves permutations of three points. Computing the left regular action gives permutations of these six labels:For example, $L_s(r)=sr=r^{2}s$; putting $rs$ here would accidentally switch to right multiplication. Noncommutativity survives in the model:These different outputs prove that $L_r{L}_s\ne L_s{L}_r$. The group generators $r,s$ become group generators $L_r,L_s$ of a six-element subgroup of $S_6$.

Why does a group action here produce a group embedding? Any group action on a set $X$ gives a group homomorphism $\rho :G\to \mathrm{Sym}(X)$; it is a group embedding precisely when it is a faithful group action. The group kernel consists of the group elements fixing every point of $X$. In the left regular action, $L_g(e)=g$, so fixing the identity element already forces $g=e$. In fact every stabilizer subgroup is trivial, since $gx=x$ forces $g=e$; this stronger property makes the left regular action a regular group action.^[ref]

Compare two group actions of the same cyclic group $C_4$. Its left regular action on four labels distinguishes all four group elements. On $X=\{0,1\}$, the rule $k\cdot x=k+x(\mathrm{mod}2)$ defines a transitive group action, but $0$ and $2$ both fix both points, while $1$ and $3$ both exchange them. Its group kernel is $\{0,2\}$, so it is not a faithful group action. Its image is a two-element subgroup of $S_2$, isomorphic to the quotient group $C_4/\{0,2\}$ rather than to $C_4$.

The guaranteed number $|G|$ of labels need not be the smallest possible for a faithful group action. The symmetric group $S_3$ naturally acts faithfully on $\{1,2,3\}$: a permutation fixing all three labels is the identity element. Its left regular action uses six labels instead. Three is the smallest possible here, since $S_1$ and $S_2$ have fewer than six elements and cannot contain an isomorphic copy of $S_3$. Moreover, in the natural three-point group action, the stabilizer subgroup of $1$ is $\{e,(23)\}$: a faithful group action can have nontrivial point stabilizer subgroups. Cayley's construction supplies a universal model, while a smaller model can reveal particular symmetries.

The proof is short. Each $L_g$ is a bijection with inverse $L_{g^{-1}}$. Associativity givesso $\lambda$ is a group homomorphism. If $L_g=L_h$, evaluating both at the identity element gives $g=L_g(e)=L_h(e)=h$. Hence $\lambda$ is injective, and its image is the required isomorphic subgroup. No finiteness assumption entered the argument.

The historical connection is unusually close to the notation. The opening paragraph of Arthur Cayley's 1854 paper already treats permutations as one example of operations on a collection of quantities and explicitly performs the rightmost operation first in a product. It also allows noncommutativity while insisting on associativity. The modern left regular action shows how that viewpoint reaches every abstract group, by choosing the group itself as the set to be acted on.^[ref]

A Cayley table records a binary operation on a finite set: the cell at row $a$, column $b$ contains $a\ast b$. Every cell must contain an element of the specified set. With the same ordering of row and column labels, the table is symmetric across its main diagonal exactly when the binary operation is commutative. Checking the associative property instead requires comparing $(a\ast b)\ast c$ with $a\ast (b\ast c)$ for every triple; symmetry alone cannot establish it.^[ref]

A circulant matrix applies the same rule at every position of a finite ring: moving both the input and output indices one step leaves its entries unchanged. Its first column determines the whole matrix. For a length-$N$ vector $c$, index rows and columns by $0,\dots ,N-1$ and defineThe indices use modular arithmetic. Thus each column is the previous column shifted down one place, with the last entry wrapping around to the top. Multiplication is exactly circular convolution:This makes a circulant matrix a natural model for a periodic finite difference rule or a filter acting on a periodic record. Strang's MIT lecture develops this connection between circulant matrices, circular convolution and the discrete Fourier transform.^[ref]

For example, the first column $c=(2,-1,0,-1{)}^T$ givesHere the indices wrap around modulo four. Each output compares a value with its two neighbors; this is the Graph Laplacian of a four-vertex cycle graph. A constant input gives zero, while an alternating input gives a large response. The Fourier diagonalization of a circulant matrix makes this distinction exact: its four eigenvalues are $0,2,4,2$.

The plotted discrete Fourier modes are complex vectors, shown through their real and imaginary parts. Each entry has modulus one; the Euclidean norm of each length-four vector is two. In particular, modes $k=1$ and $k=3$ have the same real part but opposite imaginary parts, so they are distinct eigenvectors with the same eigenvalue.

The useful surprise is that every length-$N$ circulant matrix shares the same basis of eigenvectors, whatever its first column. One change of basis therefore simplifies an entire family of linear maps, instead of requiring a separate eigenvalue computation for each one. Bamieh's tutorial develops the discrete Fourier transform from precisely this simultaneous diagonalization problem.^[ref]

A circular buffer stores a changing sequence in a fixed-capacity array, reusing slots by wrapping array indices through modular arithmetic. A front array index and an occupied count can represent a FIFO queue without shifting entries after removal. The physical array stays in place; the position at which its logical sequence begins moves. This makes a circular buffer useful when storage must remain bounded while successive items arrive and leave.

Capacity and overflow behavior are separate choices. A rejecting FIFO queue preserves all accepted items until removal and reports failure on a full insertion. An overwriting circular buffer deliberately discards its oldest item to retain the newest arrivals. These are different application programming interfaces. The existing representation independence example specifies the rejecting policy and gives its abstraction function and correctness argument against a shifting array implementation.

Let the capacity be a positive integer $C$, and allocate exactly $C$ array slots $B_0,\dots ,B_{C-1}$. Store the front array index $h$ and count $n$. The representation invariant isThe logical sequence and next-write array index areHere $\mathrm{mod}$ denotes the nonnegative remainder from modular arithmetic. The count determines which slots are live: leftover bits in other slots are not members of the FIFO queue. If $n=0$, $h$ has no current front item; it identifies the position where the next successful insertion begins. If $n=C$, $w=h$ points at a live item, so writing there requires an explicit overwrite policy.

For $n<C$, enqueue(x) writes $B_w\leftarrow x$, then increments $n$, leaving $h$ fixed. For $n>0$, dequeue() saves and returns $B_h$, then sets $h\leftarrow (h+1)\mathrm{mod}C$ and $n\leftarrow n-1$. These are sequential updates, completed before the next call. A rejecting interface tests $n=C$ or $n=0$ first and returns full or empty, respectively, without changing state. peek returns $B_h$ only when $n>0$; size returns $n$.

One can instead store $w$ and $n$, recovering $h=(w-n)\mathrm{mod}C$. On insertion, advance $w$ and increment $n$; on removal, keep $w$ fixed and decrement $n$. Thus the next-write array index is not necessarily the front array index.

Names such as head and tail require checking the actual API: the kernel documentation calls the insertion position head and the removal position tail.^[ref]

The diagram is the state after step 8 of circular buffer operation trace. Reading the physical array from slot zero would give $F,B,C,D,E$, which includes a removed label and puts $F$ first. Reading from $h$ for exactly $n$ items gives $(C,D,E,F)$. The next insertion uses slot $1$, not slot $0$. This distinction also explains why the live sequence may need two contiguous pieces of the array: here slots $2$ through $4$, followed by slot $0$. No items need to move to make this wrap work.

Circular convolution of two length-$N$ sequences uses modular arithmetic for their indices. Extending both inputs periodically gives the displayed formula. Equivalently, fold a finite discrete convolution into residue classes modulo $N$ by adding entries whose indices are congruent. The discrete Fourier transform of the circular convolution is the product of the two discrete Fourier transforms, with the usual unnormalized forward transform and $1/N$ inverse convention.

A commutative ring is a ring in which multiplication satisfies $ab=ba$ for every pair. The integers and the polynomial ring $\mathbb{Z}[X]$ are examples. So is $\mathbb{Z}/n\mathbb{Z}$, the quotient ring whose elements are residue classes in modular arithmetic. We represent these by $0,1,\dots ,n-1$ and reduce each sum or product to its remainder. All following calculations modulo $6$ use this convention.

In $\mathbb{Z}/6\mathbb{Z}$, $2\cdot 3=0$, although neither factor is zero. Thus $2$ and $3$ are zero divisors: nonzero elements whose product with another nonzero element can vanish. Also $2\cdot 1=2\cdot 4=2$. Removing the common factor $2$ would falsely assert $1=4$. The entire row for multiplication by $2$ isThe repetitions explain the linear congruences directly. The equation $2x=2$ has exactly the two solutions $x=1,4$, whereas $2x=1$ has none. A common factor can erase information, and a nonzero coefficient does not guarantee that an equation has a solution.

A unit in a ring is an element $u$ with a multiplicative inverse, meaning $uv=vu=1$ for some $v$. In $\mathbb{Z}/6\mathbb{Z}$, the units are exactly $1$ and $5$, since $5^2=1$. The other nonzero elements, $2,3,4$, are zero divisors; for $4$, use $4\cdot 3=0$. In a nonzero commutative ring, a unit cannot be a zero divisor: multiplying $ub=0$ by its multiplicative inverse forces $b=0$. But a nonzero element need not be a unit or a zero divisor: the integer $2$ is neither in $\mathbb{Z}$.

By contrast, in $\mathbb{Z}/5\mathbb{Z}$, every row for a nonzero multiplier is a permutation of $0,1,2,3,4$. Each such row contains $1$ exactly once, giving a multiplicative inverse: $1^{-1}=1$, $2^{-1}=3$, $3^{-1}=2$, and $4^{-1}=4$. Hence this commutative ring is a field. For example, $2x=1$ now has the unique solution $x=3$. Reading the tables reveals which algebraic steps the arithmetic permits.

The practical reward of quadratic reciprocity is a smaller modulus: swap a pair of distinct odd primes, record the required sign, then reduce the numerator by modular arithmetic. Use multiplicativity of the Legendre symbol and the second supplementary law for quadratic reciprocity to handle a factor of two. For example,Here $11,43$ are both $3$ modulo $4$, so the first swap changes sign; $11\equiv 3(\mathrm{mod}8)$ gives $(2/11)=-1$; the swap involving five has no sign change. An independent square check is $21^2=441\equiv 11(\mathrm{mod}43)$. The method determines existence of a square root without itself finding that root.

A composite numerator is allowed in a Legendre symbol; a composite denominator instead calls for a Jacobi symbol. Its Jacobi reciprocity law supports repeated swaps and remainder reductions, in the spirit of the Euclidean algorithm.^[ref]

A final Jacobi symbol of one is not a square-existence certificate for a composite number modulus. For example,yet $x^2\equiv 2(\mathrm{mod}15)$ is impossible: reducing it modulo three would require a square congruent to two, and squares modulo three are only zero or one. The product has hidden two local failures. By contrast, for a prime denominator, a Legendre symbol of one does certify a quadratic residue.

Two integers $a,b$ are coprime when their greatest common divisor is one:For positive integers, this says that the only positive common divisor is one. For signed integers, use $\gcd (a,b)=\gcd (|a|,|b|)$, with absolute values; changing either sign leaves coprimality unchanged. With the convention $\gcd (0,0)=0$, zero is coprime precisely to $1,-1$, because $\gcd (a,0)=|a|$. Both $1,-1$ are coprime to every integer. ^[ref]

The word concerns shared prime factors, not whether either input is a prime number. For instance $8=2^3$ and $9=3^2$ are coprime composite numbers, even though neither is a square-free integer. Conversely, $6=2\cdot 3$ and $10=2\cdot 5$ are square-free integers but are not coprime. Consecutive integers are always coprime: any common divisor of $n,n+1$ divides their difference one. Thus $14,15$ provide another pair of coprime composite numbers.

For positive integers, let $P(n)$ be the prime support of an integer. The equivalent test isThe set intersection of the two prime supports of an integer must be the empty set. Indeed, any positive common divisor greater than one has a prime factor, and any shared prime factor is a common divisor greater than one. Hence coprimality depends on which prime factors occur, rather than on their prime valuations; replacing either input by its radical of an integer preserves coprimality.

For a list of at least two integers, distinguish pairwise coprimality, requiring every pair to be coprime, from joint coprimality, requiring only the greatest common divisor of the entire list to be one. For example,No prime factor belongs to all three prime supports of an integer, yet each pair shares one. By contrast, $4,9,25$ have pairwise coprimality. The distinction is presented by Poritz under the names pairwise and mutually relatively prime. ^[ref]

One use is simplifying fractions. For a fraction $a/b$ with integer entries and $b>0$, divide its numerator and denominator by $d=\gcd (a,b)$ to obtain a reduced fraction with coprime entries. For example, $42/30=7/5$ since $d=6$, and $-42/30=-7/5$ uses the same $d$. A further common divisor would make $d$ too small, so the reduction is complete. In particular, the reduced fraction for zero is $0/1$.

Another use is reversible modular arithmetic: for an integer modulus $m>1$, an integer $a$ has a modular inverse precisely when $a,m$ are coprime. The proof outline uses Bézout's identity: $ua+vm=1$ makes $u$ a modular inverse, and any inverse relation $ua-km=1$ forces every common divisor to divide one. For example, $3\cdot 5-2\cdot 7=1$ gives $5^{-1}\equiv 3(\mathrm{mod}7)$, whereas $6$ has no modular inverse modulo $10$. Thus coprimality is the exact condition allowing division by a residue in modular arithmetic. ^[ref]

For a subgroup $H\le G$ of a group $G$, a left coset is $gH=\{gh:h\in H\}$; a right coset is $Hg=\{hg:h\in H\}$. The name refers to the side on which the representative $g$ multiplies $H$. Think of a coset as a translated copy of a subgroup: it remembers the relative differences allowed by $H$, while moving the whole collection to another location in the group.

Two left cosets of the same subgroup are either equal or disjoint. Thus distinct left cosets form a partition of a set covering $G$; the same statement holds separately for right cosets. The useful membership test isThis also defines an equivalence relation: changing a representative by right multiplication with a member of $H$ leaves its left coset unchanged. These facts hold even for infinite groups. See MIT's coset notes, definitions 3.6 and 3.9.

For an explicit additive example, take the cyclic group $G=\mathbb{Z}/6\mathbb{Z}$, with modular arithmetic, and the subgroup $H=\{0,3\}$. Adding each representative to both members gives exactlyRepresentatives $3,4,5$ repeat these three cosets, respectively. For example, $4+H=\{4,1\}=1+H$, since $4-1=3\in H$. Every residue appears once in the displayed partition of a set. Each coset has two members, so the group order of $H$ is $2$ and its index of a subgroup is $3$. Left and right cosets coincide here because $G$ is an abelian group.

A coset need not be a subgroup. In this example, $\{1,4\}$ lacks the identity element $0$, and $1+1=2$ leaves it. In fact, the only left or right coset of $H$ that is a subgroup is $H$ itself: a subgroup must contain the identity element, and the coset containing that element is $H$. Equal sizes come instead from the bijection $h\mapsto gh$, whose inverse is $x\mapsto g^{-1}x$; for right cosets, use $h\mapsto hg$ and $x\mapsto x{g}^{-1}$.

The nonabelian group $S_3$, the symmetric group on three letters, separates the two sides. Use function composition with the rightmost permutation applied first, and let $H=\{e,(12)\}$. Then $(13)(12)=(123)$ but $(12)(13)=(132)$, giving the differing pairThe complete partition of a set into left cosets consists of $H$, $\{(13),(123)\}$ and $\{(23),(132)\}$; the complete partition of a set into right cosets consists of $H$, $\{(13),(132)\}$ and $\{(23),(123)\}$. Each lists all six permutations exactly once. Both have three parts of size two, although their parts differ.

Left cosets support a group action by $a\cdot (gH)=(ag)H$ for every subgroup, as in the coset action. Multiplication of representatives defines a quotient group operation $(aH)(bH)=(ab)H$ precisely when $H$ is a normal subgroup. Otherwise the answer can depend on the representatives: in this $S_3$ example, $e$ and $(12)$ represent the same coset $H$, yet $e(13)H=(13)H$ and $(12)(13)H=(23)H$ differ. In the additive example, $H$ is a normal subgroup, making $(1+H)+(2+H)=3+H=H$ valid. See MIT's quotient-group notes, theorem 9.1.

CRYSTALS-Dilithium is a lattice-based digital signature design whose arithmetic uses vectors of polynomials modulo a fixed polynomial and integer modulus. Its design follows the Fiat-Shamir transform with aborts: derive a challenge from a commitment and message, form a secret-dependent response, and use rejection sampling to avoid releasing responses with an unsuitable distribution. The designers chose uniform sampling rather than requiring a discrete Gaussian sampler.^[ref]

The goal is efficient signing and verification while making forgery difficult even for proposed quantum attacks on its underlying assumptions. ML-DSA is the later standardized descendant. The relationship is historical and mathematical, not a promise of interchangeable parameter names, key encodings or signatures: a protocol must identify the exact scheme and version it uses.

A cyclic group is a group that can be generated by repeating a single group element $g$ and its inverse element:For an additive group, the same expression is written $\{kg:k\in \mathbb{Z}\}$: $kg$ means repeated addition, including subtraction when $k$ is negative. A finite cyclic group has a repeating cycle, while an infinite cyclic group is isomorphic to the additive integers. The notation $C_n$ refers to a finite cyclic group of order $n$.

This definition compresses a whole composition rule into one repeatable operation. Once $g$ is chosen, $g^a{g}^b=g^{a+b}$, so working with group elements becomes working with integer exponents. In the finite case those exponents are reduced using modular arithmetic. It also proves that every cyclic group is an abelian group, because $a+b=b+a$. A finite cyclic group of order $n$ has exactly $d$ solutions of $x^d=e$ for every positive integer divisor $d$ of $n$: in exponents, $n\mid dk$ has exactly $d$ solutions modulo $n$. The standard finite and infinite models are described in Group Theory (v4.01) by James S. Milne (section 1.16).

For a nonnegative integer with decimal expansion $a={\sum }_i{a}_{i}10^i$, the congruence $10\equiv 1(\mathrm{mod}d)$ gives $a\equiv {\sum }_i{a}_i(\mathrm{mod}d)$ whenever $d\mid 9$. Thus divisibility by three or nine is equivalent to divisibility of the sum of its decimal digits by the same number. More generally a base-$b$ expansion has the analogous rule for every divisor of $b-1$. This follows by repeated addition and multiplication in modular arithmetic; it does not require an empirical rule about decimal notation.

A deterministic finite automaton has exactly one automaton transition for every automaton state and input symbol. Formally, a DFA is a tuple $(Q,\Sigma ,\delta ,q_0,F)$: $Q$ is a nonempty finite set of automaton states, $\Sigma$ a finite alphabet, $\delta :Q\times \Sigma \to Q$ a function, $q_0$ the initial automaton state, and $F\subseteq Q$ the accepting automaton states. Its unique path on a word accepts if it ends in $F$ after consuming the entire input. Visiting $F$ earlier does not suffice.

For a concrete binary divisibility automaton, recognize the words whose values in the binary numeral system are divisible by three. Choose $Q=\{0,1,2\}$, $\Sigma =\{0,1\}$, $q_0=0$, and $F=\{0\}$. Each automaton state names the congruence class of the integer read so far. Appending a binary digit $b$ changes its value $n$ to $2n+b$, so the automaton transition isThe modular arithmetic therefore needs only three automaton states, whatever the input length. The full function is $\delta (0,0)=0$, $\delta (0,1)=1$, $\delta (1,0)=2$, $\delta (1,1)=0$, $\delta (2,0)=1$, and $\delta (2,1)=2$.

For $110_2=6$, the successive automaton states are $0\to 1\to 0\to 0$, so the word is accepted. For $101_2=5$, they are $0\to 1\to 2\to 2$, so it is rejected. Leading zeros are allowed: they leave the initial automaton state unchanged. We explicitly assign value zero to the empty word, which is accepted because the initial automaton state is accepting. This is a convention for a formal language, rather than a claim that ordinary written numerals include a blank numeral.

The generator checks every word of up to eight binary digits, comparing the final automaton state with the integer value modulo three. Each length $n$ includes all $2^n$ words, preserving leading zeros as distinct inputs:

All 511 checks agree. They are useful for catching a reversed arrow or mistaken label, but the reason the DFA works at every length is its invariant: after reading any word of value $n$, its automaton state is $n\mathrm{mod}3$. The update $n\mapsto 2n+b$ preserves that statement by mathematical induction. Through the extended transition function of a deterministic finite automaton, this becomes $\hat{\delta }(0,w)=\mathrm{value}(w)\mathrm{mod}3$.