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]

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.

Two equations are equivalent on a specified domain of a function if they have the same solution set. Adding the same defined mathematical expression to both sides is reversible. Multiplying or dividing both sides by a mathematical expression is reversible only where that expression is nonzero and invertible in the arithmetic being used. In a field, every nonzero scalar is invertible; a general ring needs an additional check.

For example, $x^2=1$ and $(x-1)(x+1)=0$ are equivalent equations over the real numbers, by the distributive property. Concluding $x=1$ or $x=-1$ additionally uses the absence of zero divisors. The modular example in algebra shows why that extra inference can fail in a ring with zero divisors.

A mathematical expression combines symbols according to formation rules, such as $2x+1$, $(x+1{)}^2$, or $\sqrt{x}$. With values for its variables and meanings for its algebraic operations, it can be evaluated. An equation relates two mathematical expressions; an expression alone need not assert anything.

For example, $2x+3$ evaluates to seven at $x=2$ and nine at $x=3$. Neither value solves anything until a condition is imposed: the equation $2x+3=9$ selects $x=3$ from the real numbers. This distinction is useful when moving from a formula to a question about which inputs satisfy it. Evaluation by replacing the variables with assigned values is described in College Algebra 2e, §1.1: Evaluating Algebraic Expressions.

Different written mathematical expressions can have the same value for every input in a common domain of a function. The distributive property expands $(x+1{)}^2$ to $x^2+2x+1$, while factorizing reverses that change of form. The mathematical identity between them lets one choose the form suited to the next task: the factored form exposes a multiple root at $x=-1$, and the expanded form exposes its coefficients. Simplifying should preserve values on the stated domain, rather than silently enlarging it.

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 mathematical identity is an equation that holds for every assignment in a specified domain of a function. For example, the distributive property gives $(x+1{)}^2=x^2+2x+1$ for every real number $x$. An identity can replace one mathematical expression by another without imposing a new restriction on that domain.

The domain remains essential. The equality $(x^2-1)/(x-1)=x+1$ holds for every real $x\ne 1$, but its left side is undefined at $x=1$. Cancelling a factor does not retrospectively define the original mathematical expression at the excluded input. An identity is different from an identity element of an algebraic operation or an identity function, which are separate concepts despite sharing a name.

Compute exactly three smaller products,The distributive property gives $p_s=ac+ad+bc+bd$, so the cross coefficient is $h=p_s-p_2-p_0=ad+bc$. Recombine byThe saving is that $ad$ and $bc$ are never separately multiplied. Multiplying a digit block by $q$ or $q^2$ shifts its position in positional notation; it does not require another general integer multiplication. Addition of the shifted results still requires Karatsuba carry handling.

For integrable real-valued functions $f,g$ on a measure space $(X,\mu )$ and fixed real numbers $a,b$, their linear combination $af+bg$ is integrable, and the Lebesgue integral satisfiesThe same rule applies to any finite summation: ${\int }_X{\sum }_{j=1}^n{a}_j{f}_{j}d\mu ={\sum }_{j=1}^n{a}_j{\int }_X{f}_{j}d\mu$ for integrable functions $f_j$ and fixed scalars $a_j$. Finite signed values matter: integrability ensures all these integrals are finite, so no undefined $\infty -\infty$ occurs.

This is the distributive property of finite summation carried into integration: a fixed factor can be pulled out, and a finite sum can be integrated term by term. For simple functions, distribute the finite sums of value times measure; approximation extends additivity to nonnegative measurable functions, and splitting into a positive part and negative part gives the integrable signed case. See Lecture 12: Lebesgue Integrable Functions, the Lebesgue Integral and the Dominated Convergence Theorem (Proposition 122: linearity for integrable functions). For example, ${\int }_0^1(2x-3)dx=2{\int }_0^{1}xdx-3{\int }_0^{1}1dx=-2$. With a probability measure, linearity of integration gives linearity of expectation.

In an integral domain, $ab=ac$ with $a\ne 0$ gives $a(b-c)=0$ by the distributive property. Since there are no zero divisors, $b-c=0$. Conversely, in a nonzero commutative ring, this cancellation property rules out zero divisors by comparing $ab=0$ with $a0=0$.

Under the unital ring convention used elsewhere in this wiki, no such pair exists. In a two-element ring the elements are $0$ and $1$. Additive cancellation forces $1+1=0$, and the identity axiom forces $1\cdot 1=1$. The distributive property forces products involving zero to vanish. Every operation is therefore determined, giving the prime field ${\mathbb{F}}_2$ as the unique possibility up to ring isomorphism.

If the word ring allows a nonunital ring, there are instead two non-isomorphic examples: ${\mathbb{F}}_2$ and the zero-multiplication rng on the additive group $\mathbb{Z}/2\mathbb{Z}$. In the second example the unique nonzero element $u$ satisfies $u+u=0$ and $u^2=0$; every product is zero, so associativity and both distributive laws hold. An isomorphism would have to send $1$ to $u$ because it preserves zero and is bijective, but then it would send $1^2=1$ to both $u^2=0$ and $u$, which is impossible. These exhaust the rngs with two elements, since $u^2$ can only be $0$ or $u$. Specifying the identity convention is essential for this part.

Apply the distributive property to the intersection with $\overline{C}$:In the first line the repeated factor $\overline{C}$ changes nothing. Rewriting in terms of set differences yields

Write each set difference as an intersection with a complement of a set. Applying De Morgan's laws and then the distributive property givesThe complements turn the inner union into an intersection and vice versa. Thus

An algebraic way to prove the set identity is to show that $D=\overline{A}\cup \overline{B}$ is a complement of a set for $A\cap B$. By the distributive property,andA complement of a set is unique: if $D,E$ both complement $S$, then $D=D\cap (S\cup E)=D\cap E$, and similarly $E=D\cap E$. Consequently

Distribute every term of one input across every term of the other, using the same private accumulator:

mulPoly(x,y):
    r = NIL
    p = x
    while p != NIL:
        q = y
        while q != NIL:
            accumulate(r,p.coeff*q.coeff,p.power+q.power)
            q = q.next
        p = p.next
    return r

The inner-loop invariant says that the current result contains all products from earlier nodes of x, plus the current x node multiplied by the processed prefix of y. The outer invariant is the corresponding statement for completed rows of products. The distributive property then proves correctness. Powers add, equal powers combine, zero products and cancellations disappear. Both input lists are only read, and an empty input gives the zero polynomial.

There are $mn$ coefficient products. If at most $u$ result nodes are present at a time, the simple unsorted accumulator costs $O(mn(1+u))$, with $u\le mn$; it is correct without claiming a linear-time multiplication.

Work in the finite field ${\mathbb{F}}_5=\{0,1,2,3,4\}$, using modular arithmetic modulo five. Consider the two original polynomial examplesThe distributive property gives $(x+1{)}^2=x^2+2x+1$, so all coefficients of $F$ cancel: $F$ is identically zero. In contrast, $G=x^2-3x+2=x^2+2x+2$ in this finite field, with nonzero leading coefficient. Its roots of a polynomial are exactly one and two: a product in a field is zero only if a factor is zero.

The complete polynomial evaluations, displayed as representatives modulo five, areIn particular, $G(3)=(3-1)(3-2)=2$ is a nonzero witness, which disproves identity without examining other points. At one or two, a zero value fails to reveal that $G$ is nonzero. A random variable $a$ with a uniform distribution on a finite set ${\mathbb{F}}_5$ hits those two polynomial roots with probability $2/5$.

A crucial limit appears with $H(x)=x^5-x$. Its coefficients make it a nonzero polynomial of polynomial degree five in ${\mathbb{F}}_5[x]$, yet direct polynomial evaluation gives zero at all five field elements: the values before reduction are $0,0,30,240,1020$, all divisible by five. Thus $H$ induces the same polynomial function as the zero polynomial. Any number of trials restricted to ${\mathbb{F}}_5$ will falsely accept this identity. This is compatible with the Schwartz-Zippel lemma: the ratio of polynomial degree to sampling-set size is $5/5=1$, which gives no useful guarantee.

When a polynomial's representation permits polynomial evaluation over a larger field extension, a larger sampling set can restore the useful degree ratio. Access only to the induced polynomial function on the original finite field cannot distinguish $H$ from zero.^[ref]

Polynomial multiplication combines coefficients by convolution. If $A(x)={\sum }_i{a}_i{x}^i$ and $B(x)={\sum }_j{b}_j{x}^j$, then the coefficient of $x^k$ in $AB$ is ${\sum }_{i+j=k}{a}_i{b}_j$.

For example, $(1+2x)(3-x)=3+5x-2x^2$. The coefficient rule follows from the distributive property and $x^i{x}^j=x^{i+j}$. The school method takes $O(mn)$ coefficient operations for $m,n$ coefficients; Karatsuba multiplication and Fast Fourier transforms give faster methods for large inputs. Over exact coefficient rings, transform methods must still recover exact coefficients, rather than accepting uncontrolled rounding.

A ring is a set $R$ with two binary operations, addition and multiplication, satisfying three requirements. Under addition, $R$ is an abelian group: there is a zero, every element has an inverse element, and grouping or exchanging summands does not change the result. Multiplication is associative and has an identity element $1$, so $(ab)c=a(bc)$ and $1a=a1=a$. Finally, both versions of the distributive property hold:Here every ring is unital, but the zero ring, with $0=1$, is allowed. Commutativity of multiplication is an additional condition defining a commutative ring. These conventions agree with ^[ref].

The integers form a ring with their usual operations. The polynomial ring $\mathbb{Z}[X]$ is another: addition combines coefficients, while multiplication uses the distributive property. For example,The same rules justify symbolic calculations in both rings; this is why one definition can organize apparently different kinds of arithmetic. In every ring, $a0=0a=0$, and $a(-b)=-(ab)$. The first identity follows by distributing $a(0+0)$ and subtracting $a0$; the second follows by distributing $a(b+(-b))$. Thus familiar sign rules are consequences of the structure.

Order still matters in some rings. In the matrix ring $M_2(\mathbb{R})$, takeThen matrix multiplication givesNevertheless, matrix multiplication is associative, distributes over addition, and has the identity matrix as its identity element. This is a valid ring. On a column vector, $AB$ applies $B$ first and $A$ second: swapping coordinates before discarding the second coordinate differs from doing those actions in reverse. The failure of commutativity records a meaningful difference in function composition.

A rng has an abelian group under addition, an associative multiplication, and the distributive property; a multiplicative identity element is not required. Every ring under this wiki's unital convention is a rng. A nonunital ring may happen to have an identity: the terminology removes an axiom rather than imposing the absence of an identity. For example, the even integers with their usual operations have no multiplicative identity.

Up to an operation-preserving bijection, there are two rngs with two elements. Write the elements as $0,u$. The additive abelian group must satisfy $u+u=0$. The distributive property forces all products involving zero to vanish, leaving only the choice $u^2=0$ or $u^2=u$. The first gives a zero-multiplication rng; the second gives the prime field ${\mathbb{F}}_2$, with identity $u$. Both satisfy the axioms, and they are not isomorphic because an isomorphism must send the unique nonzero element to the unique nonzero element and preserve its square. In particular, there is just one unital ring with two elements.

The sum-of-divisors function adds all positive integer divisors of a positive integer, including the number itself:It is the divisor sum of the identity arithmetic function $\mathrm{id}(n)=n$, so $\sigma =\mathrm{id}\ast 1$ under Dirichlet convolution. Both factors are multiplicative functions, hence so is the sum-of-divisors function. The notation ${\sigma }_1$ distinguishes it from other weighted divisor sums. ^[ref]

For a prime number $p$ and a nonnegative exponent $a$, the positive integer divisors of the prime power $p^a$ are precisely $1,p,\dots ,p^a$. Their finite geometric series givesFor example, $\sigma (8)=1+2+4+8=15=(2^4-1)/(2-1)$. For a prime factorization $n={\prod }_{k=1}^r{p}_k^{a_k}$ with distinct prime numbers $p_k$ and positive exponents $a_k$, multiplicativity givesFor $n=1$, this is an empty product, equal to $1$. ^[ref]

The distributive property makes the formula especially beautiful: choosing one term from each factor produces each positive integer divisor exactly once, by the fundamental theorem of arithmetic. For $12=4\cdot 3=2^2\cdot 3$, the choices form a three-by-two grid with entries $2^i{3}^j$, where $0\le i\le 2$ and $0\le j\le 1$. Adding its rows givesThe divisor function counts six cells; the sum-of-divisors function adds their six values. Once the prime factorization is known, the product formula avoids testing every candidate integer divisor. Shared prime factors require care: $\sigma (4)=7\ne 9=\sigma (2{)}^2$, so the sum-of-divisors function is not a completely multiplicative function.

Subtracting the number itself gives the proper-divisor sum $s(n)=\sigma (n)-n$. Comparing $s(n)$ with $n$ distinguishes perfect numbers, deficient numbers, and abundant numbers. For $6$, $s(6)=1+2+3=6$; for $28$, $s(28)=1+2+4+7+14=28$. Both are perfect numbers. The calculation $s(8)=1+2+4=7<8$ makes $8$ a deficient number, while $s(12)=1+2+3+4+6=16>12$ makes $12$ an abundant number. These comparisons turn the sizes of integer divisors into a classification of positive integers. ^[ref]

This connection is ancient: Euclid's Elements, Book IX, Proposition 36, constructs a perfect number by multiplying the last term of $1,2,\dots ,2^{k-1}$ by their sum, when that sum is a prime number. In modern notation, put $q=2^k-1$ and $N=2^{k-1}q$, with $k\ge 2$ and $q$ a prime number. The sum-of-divisors function proves the construction immediately:Consequently the proper-divisor sum is $s(N)=N$. Taking $k=2,3$ produces the perfect numbers $6,28$. ^[ref]