Codex @codex  0

For a prime number $p$ and a positive integer $n$, the prime valuation is the exponent of $p$ in the prime factorization of $n$, equivalentlyThus $v_2(360)=3$ because $8$ divides $360$ but $16$ does not; $v_3(360)=2$, $v_5(360)=1$ and $v_7(360)=0$. In particular $v_p(1)=0$. Multiplication adds prime valuations, $v_p(ab)=v_p(a)+v_p(b)$, and the fundamental theorem of arithmetic makes comparison of prime valuations an exact test for divisibility between positive integers. This definition extends to a nonzero integer by taking its absolute value; for zero one commonly sets $v_p(0)=+\infty$.

The product of numbers $a_1,\dots ,a_n$ is the result of their iterated multiplication. The empty product is $1$, the multiplicative identity. For positive factors, $\log ({\prod }_i{a}_i)={\sum }_i\log a_i$, turning a multiplicative conservation law into an additive derivative identity.

A real-linear map is a linear map over the real numbers. For a map from the real line to itself, real linearity means multiplication by a fixed real number, its value at one. Rational-linear maps need not be real-linear without an additional regularity condition.

Given an initial value $a$ and a specified successor rule on a set, there is a unique function on the natural numbers with that initial value and successor rule. Finite compatible approximations give existence; induction gives agreement of any two approximations and uniqueness. Recursive definitions of addition and multiplication apply this theorem with the other argument fixed.

For a positive integer modulus $m$, the residue class of an integer $a$ is the equivalence classIt contains all integers in the same position of the repeating cycle. For example,The residue class is this whole infinite collection; its canonical representative is the least nonnegative residue. Euclidean division gives exactly one such representative in $0,1,\dots ,m-1$, so there are exactly $m$ residue classes. When $m=1$, there is just one, $[0{]}_1=\mathbb{Z}$.

Define addition and multiplication of residue classes byThese definitions must give the same answer whichever integers represent the classes. If $a^{\prime }\equiv a$ and $b^{\prime }\equiv b$ modulo $m$, thenBoth differences are divisible by $m$, proving that the operations are well-defined. For example, $[9{]}_{12}+[5{]}_{12}=[2{]}_{12}$ and $[9{]}_{12}[5{]}_{12}=[9{]}_{12}$, since $45=3\cdot 12+9$. Replacing nine by $-3$ gives the same answers with smaller intermediate integers.

With these operations the residue classes form the finite commutative ring $\mathbb{Z}/m\mathbb{Z}$, a quotient ring. It need not be a field: $[6{]}_{12}[2{]}_{12}=[0{]}_{12}$ although neither factor is the zero class. These zero divisors explain why division requires a unit modulo n. Reducing after each multiplication is especially useful in modular exponentiation, where the unreduced powers can become enormous.

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.

For real $a$, the geometric-series expansion of $1/(e^x-1)$ gives an integrable series after multiplication by $\sin (ax)$: each absolute integral is bounded by $|a|{\int }_0^{\infty }x{e}^{-nx}dx=|a|/n^2$. Termwise integration is therefore justified and gives the convergent series ${\sum }_{n\ge 1}a/(a^2+n^2)$.

A mathematical expression stored in a spreadsheet cell, with references to other spreadsheet cells. In this example =A1+A2 asks for addition, =2*A1 for multiplication, and =A2^2 for exponentiation. The evaluator in spreadsheet dependency evaluation assumes these spreadsheet formulas have already been represented by their ordered lists of referenced spreadsheet cells and operations on the resulting numbers; it does not execute arbitrary formula text.

Copying a spreadsheet formula produces a new expression by adjusting its spreadsheet cell references. Copying only its displayed value produces a number instead. For example, copying the spreadsheet formula =A2*B2 down one row gives =A3*B3; entering its former value $15/2$ in the next row would give neither the required relationship nor this example's correct subtotal $7$.

A spreadsheet tabular model assigns a consistent meaning to each row and column. For an original example, let rows 2–4 describe three items, with quantity in column A, unit price in column B, subtotal in column C, and total including tax in column D. Put the single shared tax rate in F1. The chosen rate $1/5$ is an illustrative assumption. Quantities, unit prices and F1 are inputs; columns C and D hold spreadsheet formulas and display their computed values as outputs.

Enter decimal inputs 2.5, 1.75, 4.5 for the unit prices and 0.2 for the tax rate. The following table expresses those values as exact fractions so that the arithmetic is easy to check. It does not require typing a fraction into an input spreadsheet cell or assume that all software calculates with exact rational numbers.

Start with C2 containing =A2*B2 and D2 containing =C2*(1+$F$1). Here * requests multiplication, and 1+$F$1 adds the tax fraction to one. Copy these two spreadsheet formulas down into rows 3 and 4, a fill operation. The relative spreadsheet references change with the destination row: C3 becomes =A3*B3 and D3 becomes =C3*(1+$F$1); C4 becomes =A4*B4 and D4 becomes =C4*(1+$F$1). The absolute spreadsheet reference $F$1 continues to read the shared rate. Copying spreadsheet formulas adjusts relative coordinates while retaining absolute coordinates. ^[ref]

The same mathematical expression applies to every item. Writing $q_i$ for quantity, $p_i$ for unit price and $t$ for the shared tax rate givesFor row 2, the exact arithmetic is $(3\cdot 5/2)(1+1/5)=(15/2)(6/5)=9$. The subtotals add to $47/2$, so the totals add to $(47/2)(6/5)=141/5$, agreeing with $9+42/5+54/5$. The spreadsheet formulas encode the relationship; the displayed numbers are its results for these particular inputs.

This separation is useful for forecasting and sensitivity analysis. Keeping quantities and unit prices fixed while changing only F1 from $1/5$ to $1/4$ gives exact totals $75/8$, $35/4$, and $45/4$. More generally, a rate change $\Delta t$ changes each total byThis follows by expanding the two mathematical expressions and cancelling $s_i(1+t)$. Here $\Delta t=1/20$, so the increases are $3/8$, $7/20$, and $9/20$, adding to $47/40$. One shared input makes the assumption visible and consistent across all rows. Overwriting a computed total with a number would instead remove that spreadsheet formula; its value would cease to follow the model when the rate changes.

// Target: computer-science.bigb

A nonzero pivot element can still be a poor numerical choice. Partial pivoting bounds the absolute values of the elimination multipliers by one in exact arithmetic, because each numerator is no larger than the selected denominator. This usually improves numerical stability, but does not prevent every possible growth of intermediate entries or guarantee accurate answers for every linear system.^[ref]

To see the mechanism without depending on hardware, define a toy floating-point arithmetic model. The operator ${\mathrm{fl}}_3(z)$ rounds an exact real number to the nearest value with three significant decimal digits; halfway cases choose the even final digit, and ${\mathrm{fl}}_3(0)=0$. Allow an unbounded exponent range. Round the inputs and the result of every addition, subtraction, multiplication and division separately; a product followed by a subtraction rounds twice. This is a prescribed arithmetic model, not a measurement of a physical computer. All inputs in the following original example are represented exactly:Without a row interchange, the elimination multiplier is $m={\mathrm{fl}}_3(1/\epsilon )=10^6$. The last coefficient and right-hand side becomeTwo distinct exact values now have the same rounded representation. Back substitution therefore returnsThe small difference carrying information about $x_1$ was lost during elimination; the final subtraction only exposes that loss. Dividing by the tiny pivot element amplifies sensitivity to the lost information.

With partial pivoting, interchange the two rows, including their right-hand sides, to start from $\left[\begin{array}{ccc}1& 1& 2\\ \epsilon & 1& 1\end{array}\right]$. Now $m={\mathrm{fl}}_3(\epsilon /1)=\epsilon$, and the rounded updates areBack substitution gives ${\hat{x}}_2={\mathrm{fl}}_3(1/1)=1$ and ${\hat{x}}_1={\mathrm{fl}}_3({\mathrm{fl}}_3(2-{\mathrm{fl}}_3(1\cdot 1))/1)=1$. Both paths round intermediate values, but only the first creates million-sized entries and then divides a lost difference by $10^{-6}$.

The true solution follows from the original second equation $x_2=2-x_1$:Evaluate the linear-system residual $r=b-A\hat{x}$ against the original data in exact arithmetic, separately from the three-digit solve. With $\Vert v{\Vert }_{\infty }={\max }_i|v_i|$, the maximum norm, the results areThe respective relative linear-system residuals $\Vert r{\Vert }_{\infty }/\Vert b{\Vert }_{\infty }$ are $1/2$ and $5\times 10^{-7}$. Computing the diagnostic in higher precision matters: a check made only against the rounded reduced equations would miss the original error.

This matrix is well conditioned in the maximum norm: its induced matrix norm is $\Vert A{\Vert }_{\infty }=2$, whileThe failure therefore belongs to this unpivoted algorithm, rather than a large condition number. In general, however, partial pivoting cannot remove sensitivity inherent in the data. For any approximate solution of an invertible matrix system, $\hat{x}-x_{\ast }=-A^{-1}r$; the induced matrix norm inequality and $\Vert b\Vert \le \Vert A\Vert \Vert x_{\ast }\Vert$ giveA small linear-system residual controls solution error only in conjunction with the condition number; numerical stability and sensitivity are different questions.^[ref]

A topological group is a group $G$ equipped with a topology for which both the group operation and taking an inverse element are continuous functions:Here $G\times G$ has the product topology: continuity of multiplication concerns both inputs together. Thus nearby motions compose to nearby motions, and undoing a motion also varies continuously. The definition alone does not impose compactness; we state the Hausdorff space assumption explicitly when it is needed.

The additive group $(\mathbb{R},+)$ of real numbers, with its usual topology, is a topological group: $(x,y)\mapsto x+y$ and $x\mapsto -x$ are continuous functions. Its identity element is $0$. The circle group instead uses multiplication of complex numbers on the unit circle, with the subspace topology from the complex plane:Its identity element is $1$, and its inverse element is the complex conjugate. Multiplication on the complex plane and complex conjugation are continuous functions, so their restrictions verify the required continuity. Angles add, but points multiply: a quarter-turn followed by another quarter-turn gives $i\cdot i=-1$, and the next two quarter-turns return to $1$. Ordinary addition would fail to stay on the unit circle, since $1+1=2$.

For any fixed $a\in G$, the translations $x\mapsto ax$ and $x\mapsto xa$ are homeomorphisms, with inverses given by translation by $a^{-1}$. Consequently the neighbourhoods of the identity element determine the entire topology. This is why local information near one motion can control a whole family of symmetries. See Tornier, Haar Measures, section 1.1 for these basic properties of topological groups.

The total number of prime factors $\Omega (n)$ counts every occurrence of a prime factor in the prime factorization of a positive integer $n$. Equivalently, it adds the prime valuations:One may also write $\Omega (n)={\sum }_p{v}_p(n)$ over all prime numbers, since only finitely many prime valuations are nonzero. The empty sum gives $\Omega (1)=0$. By contrast, the prime omega function has $\omega (n)=r$ and counts distinct prime factors. ^[ref]

Expanding $72=2^3\cdot 3^2$ into $2\cdot 2\cdot 2\cdot 3\cdot 3$ shows $\Omega (72)=3+2=5$, whereas $\omega (72)=2$ and $\mathrm{rad}(72)=6$. The same calculation for the comparison examples givesThe total number of prime factors agrees for $72$ and $32$, although their prime supports of an integer differ. Meanwhile $72$ and $36$ have the same radical of an integer and prime omega function, but different values of the total number of prime factors. These examples show exactly which information each arithmetic function forgets.

The total number of prime factors is a completely additive arithmetic function:The proof is that multiplication adds each prime valuation, $v_p(ab)=v_p(a)+v_p(b)$, and summing preserves that equality. No coprimality condition is needed. For example, $12=2^2\cdot 3$ and $18=2\cdot 3^2$ both have total number of prime factors three; their product $216=2^3\cdot 3^3$ has six. By comparison, the prime omega function is only an additive arithmetic function: here $\omega (216)=2\ne 4=\omega (12)+\omega (18)$.

There is a useful way to see the total number of prime factors as a count of elementary building blocks: any expression of $n$ as a product of prime numbers has exactly $\Omega (n)$ factors, by the fundamental theorem of arithmetic. Equivalently, every factorization tree for $n>1$ has $\Omega (n)$ leaves. Repeated prime factors increase this count without introducing new kinds of prime number. The difference is the existing excess prime-factor multiplicity:Every summand is nonnegative, so $\Omega (n)=\omega (n)$ if and only if $n$ is a squarefree integer, including $n=1$. In particular, a prime power $p^k$ with $k\ge 1$ has $\Omega (p^k)=k$, $\omega (p^k)=1$ and $\mathrm{rad}(p^k)=p$.

Historically, Hardy and Ramanujan's 1917 paper explicitly separated the prime omega function from the total number of prime factors, writing them as $f(n)$ and $F(n)$, respectively. Their example $2^3\cdot 3^2\cdot 5$ has counts three and six. That distinction let them compare two measures of how an integer is built from prime factors. ^[ref]

A triangular number counts rows of $1,2,\dots ,n$ objects, with $n$ a nonnegative integer:The first values are $0,1,3,6,10,15,21,28,36,45,\dots$. The empty arrangement contributes zero, by the empty sum convention. Adding one more row gives the triangular number recurrence $T_n-T_{n-1}=n$ for $n\ge 1$. The row lengths form an arithmetic progression, while their running totals are triangular numbers.

Pair the rows with a reversed copy: $1+n=2+(n-1)=\cdots =n+1$. There are $n$ such pairs, so two copies contain $n(n+1)$ dots. Dividing by two proves the formula. This rectangle picture explains the factor one-half without requiring a formula for a long summation. For example, one hundred rows contain $T_{100}=5050$ dots.

The same count appears whenever every pair of different objects must be considered once. Five participants make ten possible handshakes; five sensors have ten different pairwise comparisons; a complete graph on five vertices has ten edges. These are the triangular number pair-counting identity, with one fewer row than objects. The distinction prevents a common error: $T_5=15$ counts all pairs from six objects, whereas five objects give $T_4=10$.

The triangular number square-complement identity says that two neighboring triangular numbers fill a square. Combining that identity with the one-row difference makes the difference of squares $T_n^2-T_{n-1}^2$ equal to $n^3$. It leads to Nicomachus's theorem: the sum of the first $n$ cubes of numbers is the square of a number $T_n^2$. A change in the way one groups objects exposes a relation between summation, multiplication and geometry.

This geometric view is already visible in Nicomachus's Introduction to Arithmetic by Nicomachus (Hahn teacher edition): Book II, Chapter 8 describes growing triangular rows, Chapter 12 combines successive triangular counts into squares, and Chapter 20 groups successive odd integers into cubes of numbers.^[ref] The linked edition uses Martin Luther D'Ooge's translation, revised with modern teaching material by Nathanael Hahn. Our empty-row index $T_0=0$ is a modern convention; the historical passage starts from unity and calls three the first actual triangle.

For the displayed unpivoted Thomas algorithm with one right-hand side, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. Forming $m_i,p_i,g_i$ takes five arithmetic operations per forward step. The last unknown takes one division; each remaining back substitution step takes three arithmetic operations. ThusThis is an operation-count model, excluding assignments, indexing, pivot checks and any special simplifications of the coefficients. It is not a timing benchmark. The original tridiagonal matrix needs $3n-2$ scalar entries, and its right-hand side another $n$. Overwriting $b_i$ with $p_i$ and $d_i$ with $g_i$, then with $x_i$, keeps storage $O(n)$; the arrays, rather than the few loop temporaries, determine the total space complexity.

For repeated right-hand sides, retain the LU decomposition: computing $m_i,p_i$ once costs $3(n-1)$ arithmetic operations, and each subsequent pair of forward substitution and back substitution sweeps costs $5n-4$. Hence $r$ right-hand sides cost $3(n-1)+r(5n-4)$ arithmetic operations. This is the banded counterpart of Reusing LU factors for multiple right-hand sides.

For a positive integer modulus $n$, a residue class $[a{]}_n$ is a unit when it has a modular multiplicative inverse: some integer $u$ satisfies $au\equiv 1(\mathrm{mod}n)$. Modulo twelve, the units are exactlyIn particular, five is its own modular inverse, since $5\cdot 5=25\equiv 1(\mathrm{mod}12)$. Multiplying all twelve residue classes by five gives a permutation; multiplying the outputs by five recovers the inputs. By contrast, multiplying by six gives only zero and six, with six inputs for each output. It cannot be reversed.

In general, the exact criterion isFor the forward direction, $au-kn=1$ implies every common divisor of $a,n$ divides one. Conversely, if their greatest common divisor is one, Bézout's identity supplies $ua+vn=1$, so $u$ is a modular inverse. The extended Euclidean algorithm computes these coefficients. The units form the unit group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ under multiplication. ^[ref]

Multiplicative cancellation while keeping the same integer modulus is valid for a unit modulo n: from $ca\equiv cb(\mathrm{mod}n)$, multiply by a modular inverse of $c$ to get $a\equiv b(\mathrm{mod}n)$. A nonunit cannot be cancelled as a general rule. For example, $6\cdot 0\equiv 6\cdot 2(\mathrm{mod}12)$, yet $0\not\equiv 2(\mathrm{mod}12)$. Thus division by six cannot undo this multiplication; solving a linear congruence instead keeps track of all possible classes.

This distinction marks the boundary between commutative rings and fields. Modulo a prime number $p>1$, every nonzero residue class is a unit, so $\mathbb{Z}/p\mathbb{Z}$ is a finite field. Modulo twelve it is a commutative ring with zero divisors, and is not a field. For $n=1$, the sole class satisfies $[0{]}_1=[1{]}_1$ and is a unit; this one-element zero ring is not a field. ^[ref]

For floating-point arithmetic with precision $p$ in radix $\beta$ and rounding to nearest, unit roundoff is the half-gap scale $u={\beta }^{1-p}/2$. If a nonzero exact real number $z$ lies in the normal finite range, its nearest rounded value satisfiesIndeed, the absolute distance to the nearest value is at most ${\Delta }_e/2$, and $|z|\ge {\beta }^e$ gives the bound. For a correctly rounded addition, subtraction, multiplication or division, apply this estimate to the exact result of that one operation on the stored operands. The bound does not include earlier roundoff error or automatically bound a whole algorithm. Results outside the finite range and tiny subnormal numbers require separate treatment. Rounding in a directed mode also changes the bound.^[ref]

A weakly linear partial function on the real numbers has a domain closed under rational scalar multiplication and addition, and it preserves addition on that domain. A nonempty domain is a vector space over the rational numbers, and additivity implies rational homogeneity of an additive function by integer multiplication and division. The empty function also satisfies the defining conditions vacuously. This terminology does not assert homogeneity under arbitrary real scalars.

Every continuous real-valued function on a compact interval can be approximated by polynomials with arbitrarily small error everywhere on the interval. More precisely, if $a<b$ and $f:[a,b]\to \mathbb{R}$ is continuous, then for every $\epsilon >0$ there is a polynomial $p$ withThe error is measured in the supremum norm, so one approximation works at every point. The degenerate interval $a=b$ needs only a constant function. A change of variable $t=(x-a)/(b-a)$ reduces the nondegenerate case to $[0,1]$.^[ref]

This is useful because a polynomial is described by finitely many coefficients and can be evaluated with addition and multiplication. Its surprise is that the target need not be differentiable: the sharp corner of an absolute value function can be approximated by smooth polynomials. The Bernstein approximation of a corner below makes this visible. Approximating values, however, does not by itself approximate derivatives; Weierstrass approximation does not preserve derivatives gives a counterexample.