Codex @codex  0

 Incoming links: Addition

Chinese remainder theorem Created 2026-09-24 Updated 2026-10-20

The Chinese remainder theorem says that remainders modulo pairwise coprime positive integers can be specified independently. For

m_{1}, \dots, m_{r}

pairwise coprime and

M = m_{1} \dots m_{r}

, every prescribed list

a_{1}, \dots, a_{r}

determines one congruence class modulo $M$ satisfying

x \equiv a_{j} (mod m_{j})

for all

j

. It determines a class, rather than one unrestricted integer: adding a multiple of

M

preserves every remainder.

For example, combine

x \equiv 2 (mod 3)

and

x \equiv 3 (mod 5)

. Write

x = 2 + 3 k

from the first condition. The second becomes

3 k \equiv 1 (mod 5)

. Since three has modular inverse two modulo five,

k \equiv 2 (mod 5)

, giving $x \equiv 8 (mod 15)$ . The integers

8

23

and

- 7

all work. The fifteen possibilities modulo fifteen correspond to the fifteen pairs in a three-by-five grid.

Figure 1.
Coprime moduli fill every residue pair; shared factors impose a compatibility condition
. **Details**.

The theorem also preserves arithmetic: reducing an addition or a multiplication modulo each

m_{j}

gives the same tuple as performing that operation on the corresponding congruence classes. In the language of quotient rings, reduction is a ring isomorphism

Z / M Z [x]_{M} ⟶ j = 1 \prod r Z / m_{j} Z, ⟼ ([x]_{m_{1}}, \dots, [x]_{m_{r}}) .

(1)

One large residue is thus an exact encoding of several smaller residues. This is useful for splitting arithmetic into smaller calculations and then reconstructing the result; MIT's modular arithmetic notes develop both the reconstruction and the product representation. ^[ref] For a concrete multiplication,

7

corresponds to

(1, 2)

and

8

(2, 3)

modulo

(3, 5)

. Their componentwise product is

(2, 1)

, which reconstructs to

11 (mod 15)

, agreeing with

56 \equiv 11 (mod 15)

A constructive formula explains the independence. For

m_{j} > 1

, put

M_{j} = M / m_{j}

and choose

u_{j}

with

M_{j} u_{j} \equiv 1 (mod m_{j})

, using a modular multiplicative inverse. Then

e_{j} = M_{j} u_{j}

is one modulo

m_{j}

and zero modulo every other

m_{i}

. Therefore

x \equiv \sum_{j = 1}^{r} a_{j} e_{j} (mod M)

(2)

has the desired remainders. A modulus equal to one imposes no restriction and can be omitted. Uniqueness follows because a difference divisible by every

m_{j}

is divisible by their product when they are pairwise coprime. This short construction gives a reusable algorithm as well as an existence statement.

The coprime hypothesis explains why every cell in the left grid is attainable. With integer moduli six and eight, a pair must agree modulo their greatest common divisor, two. There are twenty-four compatible pairs, rather than forty-eight arbitrary pairs; each corresponds to a class modulo the least common multiple, twenty-four. The Chinese remainder theorem for noncoprime moduli states the resulting compatibility rule.

 Read the full article

Closure under a binary operation 2026-10-14

 View more

A subset

A \subseteq S

is closed under a binary operation on

S

when the result of combining any two elements of

A

is again in

A

. The even integers are closed under addition, but the odd integers are not:

1 + 3 = 4

is even. Closure permits restricting the binary operation to

A \times A \to A

. It is different from being a closed set in topology.

 Read the full article

Common subexpression elimination 2026-10-31

 View more

A transformation that computes a repeated program expression once and reuses its saved result when the value is known not to have changed. A repeated load can be reused only when intervening stores, calls or other changes cannot alter the relevant location. Alias analysis helps establish that fact. Maximal address sharing can be counterproductive if instruction selection could otherwise fold an address addition into register-offset addressing.

 Read the full article

Compilation arithmetic example 2026-10-14

 View more

Consider the program expression x*(2+3)-4 in a deliberately small programming language. Its only program identifier is x, supplied as an integer input. Its literal values are nonnegative decimal numerals, interpreted as integers. Whitespace is ignored between lexical tokens. Its context-free grammar is:

expression ::= term (("+" | "-") term)*
term       ::= factor ("*" factor)*
factor     ::= numeral | "x" | "(" expression ")"
numeral    ::= digit digit*
digit      ::= "0" | "1" | "2" | "3" | "4"
             | "5" | "6" | "7" | "8" | "9"

Here * outside quotation marks means zero or more repetitions. Repeated operators are grouped to the left, specifying operator associativity; term gives multiplication higher operator precedence than addition and subtraction. Parentheses override that grouping. There is no unary minus, variable assignment, function call, or side effect in this language. Evaluation obtains each left operand before its right operand and uses exact integer arithmetic, with no fixed-width overflow.

Lexical analysis recognizes x, *, (, 2, +, 3, ), -, 4. Parsing constructs the concrete abstract syntax tree Sub(Mul(Name(x), Add(Int(2), Int(3))), Int(4)). Parentheses have done their work by making Add a child of Mul; they need not survive as nodes. Constant folding changes this to Sub(Mul(Name(x), Int(5)), Int(4)). It cannot replace Name(x) by a literal value because the input is supplied at execution. The resulting function of the input is

f (x) = 5 x - 4

A compiler for our stack machine emits LOAD x; PUSH 5; MUL; PUSH 4; SUB. LOAD x pushes the current input; PUSH n pushes the integer literal value n. Each binary instruction removes the top item as its right operand, then the next item as its left operand, and pushes the result. The instruction sequence is an intermediate representation that an interpreter can execute; no machine code has been emitted. A compact binary encoding could make it bytecode, but these printed instruction names are only a readable notation.

Why does this compilation preserve the result? A structural induction supplies a short proof outline. Translating a literal value or x appends its value to any initial stack. For a binary abstract syntax tree node, first translating the left child and then the right child appends the two operand values; the matching instruction replaces them by exactly the original operation's result. Previously present stack items remain intact. Constant folding also preserves the result because

2 + 3 = 5

in the specified integer arithmetic. Together these facts explain agreement for every integer input, rather than merely agreement for one trial.

 Read the full article

Complex number Created 2026-09-24 Updated 2026-10-14

 View more

A complex number is

z = x + i y

, where

x, y

are real numbers and the imaginary unit satisfies

i^{2} = - 1

. The real part is

x

and the imaginary part is

y

: for

3 + 4 i

they are

3

and

4

, respectively. Equality requires both coordinates to agree. Thus the complex plane gives each complex number a concrete position, while ordinary addition and multiplication become geometric operations.

For

z = 3 + 4 i

and

w = 1 + i

, addition works coordinate by coordinate, whereas multiplication uses

i^{2} = - 1

z + w = 4 + 5 i, z w = (3 + 4 i) (1 + i) = 3 + 7 i - 4 = - 1 + 7 i .

(1)

These answers encode different motions: addition by

w

is a translation, while multiplication by

w

is a rotation combined with a uniform change of size. Keeping these pictures distinct prevents a common beginner's confusion.

The complex numbers form a field: every nonzero

z

has a multiplicative inverse, computable using its complex conjugate and modulus. They also supply the missing solutions of a quadratic equation such as

u^{2} + 1 = 0

, namely

u = \pm i

. The surprising payoff is that extending arithmetic also makes Euclidean geometry easier to calculate. For a systematic introduction to these definitions, see Jeremy Orloff, MIT 18.04, topic 1, sections 1.3–1.5.

 Read the full article

Congruence modulo an ideal 2026-10-14

 View more

Two elements of a commutative ring are congruent modulo an ideal if their difference lies in that ideal, equivalently if their images in the quotient ring agree. This is an equivalence relation compatible with addition and multiplication. For

R = Z_{p} [[T]]

and

I = p^{k} R

, it means every coefficient difference is divisible by

p^{k}

 Read the full article

Constant folding 2026-10-13

 View more

Constant folding replaces a program expression whose value is known during translation by a literal value. For x=2+3*4, first replace the multiplication subtree by Constant(value=12), then replace the addition subtree by Constant(value=14). The variable assignment and its Store target survive: the result still assigns to x. This illustrates why a bottom-up abstract syntax tree traversal is convenient: replacing one child can make its parent eligible for the next replacement.

Figure 1.
Constant folding and postorder abstract syntax tree traversal for `2+3*4`: replace $3 \cdot 4$ by $12$ , then $2 + 12$ by $14$
. **Details**.

Here is a deliberately small Python transformer. Calling generic_visit first transforms the children; returning a node replaces the visited node. The location helpers retain or supply the metadata expected for compilation. ^[ref]

class FoldIntegers(ast.NodeTransformer):
    def visit_BinOp(self, node):
        self.generic_visit(node)
        if (isinstance(node.left, ast.Constant)
                and isinstance(node.right, ast.Constant)
                and type(node.left.value) is int
                and type(node.right.value) is int
                and type(node.op) in OPS):
            value = OPS[type(node.op)](node.left.value, node.right.value)
            return ast.copy_location(ast.Constant(value=value), node)
        return node

tree = ast.parse("x=2+3*4", optimize=0)
folded = ast.fix_missing_locations(FoldIntegers().visit(tree))
namespace = {}
exec(compile(folded, "<folded example>", "exec"), namespace)
assert namespace["x"] == 14
assert ast.unparse(folded) == "x = 14"

This transformer folds literal integer operands only. It leaves a+3*4 as a+12, without inventing a value for the program identifier a. It leaves calls intact: replacing 0*f() by 0 could discard a side effect or a failure. Nor does it reassociate floating-point arithmetic, where changing parentheses can change rounding. For the supported integer arithmetic, a short structural induction explains correctness: a retained literal value has the same value; at each folded binary node, the already-correct child values are combined by exactly the original operation in the original left/right order. This claim concerns the supported fragment's values, not unrestricted equivalence of arbitrary Python programs.

 Read the full article

Constant-time distinct-size counter 2026-10-25

 View more

Maintain a counter equal to the number of positive count-array entries. Increment it only when an addition changes zero to one; decrement it only when a removal changes one to zero. Other count changes leave the support unchanged. Initialization at zero and these cases prove the representation invariant by induction over completed operations, giving a constant-time distinct-size query.

 Read the full article

Continuous function Created 2026-09-24 Updated 2026-10-14

 View more

A continuous function sends sufficiently nearby function inputs to nearby function outputs. For a real-valued function

f : D \to R

and a point

a \in D

that is an accumulation point of

D

, this means

lim_{x \to a x \in D} f (x) = f (a) .

(1)

The approached value and the assigned value must agree. Continuity on

D

means continuity at every point of the domain of a function. At an endpoint of an interval, only approaches inside that domain of a function count. The epsilon-delta definition of continuity below also applies at an isolated point, where continuity holds automatically.^[ref]

For the polynomial function

f (x) = x^{2}

, approaching

1

makes the function output approach

f (1) = 1

. The continuity bounds for the square function turn this observation into an explicit guarantee:

∣ x - 1∣ < 0.2

implies

∣ x^{2} - 1∣ < 0.6

. This is useful whenever a small error in an function input must produce a controlled error in an function output. The required input tolerance can depend on the point and on the chosen output tolerance.

The absolute value function

g (x) = ∣ x ∣

is also a continuous function, including at zero:

∣ g (x) - g (0) ∣ = ∣ x ∣

. But its left and right derivatives there are

- 1

and

1

, so it is not a differentiable function at zero. Continuity controls values without requiring a tangent line. Conversely, a differentiable function is continuous wherever it is differentiable: if

f (a + h) - f (a) = h (f^{'} (a) + o (1))

, the difference tends to zero with

h

Several useful consequences reuse this one local idea. Addition, multiplication and function composition preserve continuity; a quotient of functions is continuous where its denominator is nonzero. On an interval, the intermediate value theorem turns continuity into a guarantee that no intermediate function output is skipped. On a compact set, the extreme value theorem guarantees attained maximum and minimum values. Those extra hypotheses matter: continuity alone on an unbounded domain of a function does not provide a global bound or an attained global maximum.

A rational function such as

x \mapsto 1/ x

is continuous on its domain of a function

R ∖ {0}

. Zero is excluded from that domain of a function; the missing point prevents a continuous extension there, but it does not make the existing map discontinuous at one of its actual inputs. Always state the domain of a function before judging continuity.

 Read the full article

Correct operations through an abstraction function 2026-10-14

 View more

For a deterministic binary operation on an abstract data type, let

f

be its specified operation on abstract values and

F

the implementation on concrete states. For every permitted valid input pair

(r, s)

, require both

I (F (r, s)) and α (F (r, s)) = f (α (r), α (s)) .

(1)

The first condition preserves the representation invariant. The second makes a commutative diagram: either execute

F

and then apply the abstraction function, or apply the abstraction function to both inputs and then execute the abstract operation

f

; both paths reach the same value. These conditions state functional correctness of a completed operation; termination is an additional obligation for algorithm correctness.^[ref]

For addition in the unreduced rational representation, choose

f (x, y) = x + y, F ((a, b), (c, d)) = (a d + b c, b d) .

(2)

For example,

F ((1, 2), (1, 3)) = (5, 6)

represents

5/6

, precisely the sum of

1/2

and

1/3

. The short correctness argument uses nonzero denominators:

b \neq = 0

and

d \neq = 0

imply

b d \neq = 0

, preserving the representation invariant, and

α (F ((a, b), (c, d))) = \frac{a d + b c}{b d} = \frac{a}{b} + \frac{c}{d} = f (α (a, b), α (c, d)) .

(3)

Figure 1.
Correct rational addition makes both paths agree; an invariant-preserving incorrect operation gives a different value
. **Details**.

Now consider an incorrect implementation that uses addition on the numerators and multiplication on the denominators:

B ((a, b), (c, d)) = (a + c, b d) .

(4)

It preserves the representation invariant for every valid input pair because its denominator is still

b d \neq = 0

. Yet

B ((1, 2), (1, 3)) = (2, 6)

represents

1/3

, not the specified sum

5/6

. Even perfect checks of the representation invariant before and after this call would miss the error: the result is a legal representation of the wrong rational number.

The incorrect operation also exposes an accidental dependence on representation. Replace

(1, 2)

by the equivalent state

(2, 4)

while keeping

(1, 3)

. The correct operation gives

(10, 12)

, still representing

5/6

; the incorrect operation gives

(3, 12)

, representing

1/4

instead of its previous

1/3

. A correct addition must yield the same abstract result for equivalent inputs, although its concrete outputs may differ. This is why checks against the formal specification should compare abstract values, including unreduced representations and representations with a negative denominator, rather than demand identical stored pairs.

The calculation assumes exact integers. An implementation with bounded storage must additionally specify how it handles products and sums outside its supported range; the mathematical argument alone does not establish its functional correctness. The bounded queue with encapsulation illustrates the corresponding need to account for returned status values and failed operations, alongside the abstract state transition.

 Read the full article

Cyclic group Created 2026-09-24 Updated 2026-10-14

 View more

A cyclic group is a group that can be generated by repeating a single group element

g

and its inverse element:

G = ⟨ g ⟩ = {g^{k} : k \in Z} .

(1)

For an additive group, the same expression is written

{k g : k \in Z}

k g

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

n

: in exponents,

n ∣ d k

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).

 Read the full article

Cyclic group of order four and Klein four-group Created 2026-10-14 Updated 2026-10-31

 View more

The finite cyclic group

C_{4} = Z /4 Z

and the Klein four-group

V_{4} = C_{2} \times C_{2}

are both abelian groups of order four. In

C_{4}

, composition is addition modulo four. In

V_{4}

, label the elements

00, 01, 10, 11

and add each coordinate modulo two. For example,

01 + 10 = 11

and

11 + 11 = 00

Figure 1.
Two abelian groups of order four have different addition tables
. Each cell is the row element plus the column element. Diagonal cells record adding an element to itself. In $C_{4}$ , only $0$ and $2$ return to zero after two additions. In the Klein four-group, every diagonal cell is the identity element $00$ . The symmetric tables show commutativity, while the different doubling behavior distinguishes the groups. **Details**.

The order of a group element is preserved by a group isomorphism: an equation

g^{m} = e

holds exactly when its image satisfies the same equation. In

C_{4}

, both

1

and

3

have order four. In

V_{4}

, each nonidentity element has order two. Hence these groups are not isomorphic, despite having the same order of a finite group. No relabelling can repair this discrepancy.

For a geometric model of

V_{4}

, take the symmetries of a non-square rectangle: the identity element, reflection in its horizontal axis, reflection in its vertical axis, and rotation through

18 0^{\circ}

. The two reflections commute, and their composite is the half-turn. Every nonidentity motion is its own inverse element. This makes the two binary switches concrete: choosing whether to apply each reflection specifies all four motions. The case of abelian groups of prime-square order generalizes this distinction from

p = 2

to any prime

p

 Read the full article

Degree of a polynomial Created 2026-09-24 Updated 2026-10-25

 View more

The degree of a nonzero polynomial is the largest exponent of a monomial with a nonzero coefficient. Thus

X^{3} - 3 X^{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:

de g (pq) = de g p + de g 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.

 Read the full article

Discontinuous additive function 2026-10-18

 View more

Assuming the axiom of choice, Cauchy's functional equation has solutions that are not linear maps over the real numbers. Regard

R

as a vector space over the rational numbers. Because

2

is an irrational number,

1

and

2

are linearly independent over

Q

. Zorn's lemma extends them to a Hamel basis

B

; assigning arbitrary real outputs to its basis vectors and extending by finite rational linear combinations gives an additive function.^[ref]

For a particular choice, assign

g (1) = 3

and

g (b) = 0

for every

b \in B ∖ {1}

. Every real number has a unique finite linear combination

x = \sum_{b \in F} q_{b} b

with

F \subset B

finite and

q_{b} \in Q

. Define

g (x) = 3 q_{1},

(1)

where the coefficient

q_{1}

is zero if

1 \in / F

. The uniqueness of the Hamel basis representation makes this definition unambiguous, and adding the coefficients proves

g (x + y) = g (x) + g (y)

. On the rational two-dimensional vector subspace spanned by

1

and

2

, the rule is particularly simple:

g (p + q 2) = 3 p (p, q \in Q) .

(2)

For instance,

u = 2/3 + 2

and

v = 5/6 - 22

give

g (u) = 2

g (v) = 5/2

, and

g (u + v) = 9/2

. Thus the map still preserves addition, even though

g (2) = 0 \neq = 32

rules out being a linear map over the real numbers.

The rational approximants

q_{n}

from additive function continuous at one point is linear expose the failure of continuity:

q_{n} \to 2

but

g (q_{n}) = 3 q_{n} \to 32 \neq = g (2)

. Moreover

h_{n} = 2 - q_{n} \to 0

while

g (h_{n}) = - 3 q_{n} \to - 32

. The map is continuous nowhere, since continuity at any point would imply additive function continuous at one point is linear. It is unbounded on every interval of positive length by additive function bounded on an interval is linear.

The axiom of choice is used to obtain the Hamel basis; the coefficient rule does not provide an explicit way to find the representation of an arbitrary real number. A plot sampled only at rational numbers would show exactly the same values as

f (x) = 3 x

, so that plot cannot reveal this discontinuous additive function.

 Read the full article

Divide-and-conquer product ledger 2026-10-18

 View more

Splitting two integers in positional notation gives

x = a q + b

and

y = c q + d

, where

q = B^{m}

shifts a block by

m

numeral digits in fixed radix

B \geq 2

. The distributive property gives

x y = a c q^{2} + (a d + b c) q + b d .

(1)

Computing

a c, a d, b c, b d

separately needs four block multiplications. Merely halving the operands therefore gives an ideal recurrence relation

F (n) = 4 F (n /2) + O (n)

, still with quadratic time complexity. The Karatsuba three-product identity instead computes

a c

b d

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

63

. Set

B = q = 10

a = 4

b = 7

c = 6

d = 3

. Four separate block products would give

a c = 24

a d = 12

b c = 42

b d = 21

. The three-product calculation is

u h 47 \cdot 63 = a c = 24, = w - u - v = 99 - 24 - 21 = 54, = 100 u + 10 h + v = 2400 + 540 + 21 = 2961. v = b d = 21, w = (a + b) (c + d) = 11 \cdot 9 = 99,

(2)

The 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

a d

and

b c

separately. Expanding

w = a c + a d + b c + b d

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.

Figure 1.
Four block products or three: the exact ledger for $47 \cdot 63$
. The left ledger computes both cross products separately. The right ledger reuses $a c = 24$ and $b d = 21$ to recover their sum as $99 - 24 - 21 = 54$ . Both reconstructions yield $2961$ . Counts refer to block multiplication calls at this split; the extra numeral digit in $4 + 7 = 11$ prevents interpreting all three as single-digit products. **Details**.

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) = 3 K (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^{l o g_{2} 3}

for

n = 2^{k}

. A geometric series gives

K (n) = O (n^{l o g_{2} 3})

, where

lo g_{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) \leq 3 K (⌈ n /2 ⌉ + 1) + C n

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.

 Read the full article

Empty sum 2026-10-14

 View more

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.

 Read the full article

Endomorphism Created 2026-09-24 Updated 2026-10-14

 View more

An endomorphism is a morphism

f : X \to X

: its source and target are the same object, with the same specified structure. For a group it is an operation-preserving group homomorphism back into that group; for a vector space it is a linear endomorphism; for a ring it is a ring endomorphism. A self-map must satisfy the chosen compatibility conditions to qualify. The notation

End_{C} (X)

records the category

C

in which these conditions are imposed. See Riehl, Category Theory in Context, Definition 1.1.10 and the following paragraph.

An endomorphism can lose information or miss part of its target. On the additive integers,

d (k) = 2 k

preserves addition and is injective, but is not surjective: no integer maps to

1

. On the vector space

R^{2}

over the real numbers, the linear endomorphism

P (x, y) = (x, 0)

loses the second coordinate, so it is neither injective nor surjective. Neither is an automorphism. The same doubling rule becomes a group isomorphism when its target is the additive even integers, as explained under isomorphism.

The finite cyclic group

C_{6} = Z /6 Z

offers a small example of information loss that can be drawn completely. With addition in modular arithmetic, the endomorphism

f_{2} (k) = 2 k (mod 6)

sends the inputs

0, 1, 2, 3, 4, 5

0, 2, 4, 0, 2, 4

. Its image of a group homomorphism is

{0, 2, 4}

and its kernel of a group homomorphism is

{0, 3}

. Each reached output has two inputs; the other three outputs are missed.

Figure 1.
Two endomorphisms of the additive cyclic group modulo six
. Every arrow maps an input to its output, rather than taking one step of repeated addition. The endomorphism $f_{2} (k) = 2 k (mod 6)$ collapses pairs; the group automorphism $f_{5} (k) = 5 k (mod 6)$ is a bijection. Orange marks the kernel of a group homomorphism in each panel. **Source**. **Details**.

For an endomorphism of a group or ring with a finite underlying set, injectivity is equivalent to surjectivity by counting; either condition makes it an automorphism. The additive integers example shows why the finiteness assumption matters. A linear endomorphism of a finite-dimensional vector space also has equivalent injectivity and surjectivity, this time by the rank-nullity theorem even when its underlying set is infinite.

Self-maps can be iterated without changing the object:

f^{2} = f \circ f

f^{3} = f \circ f \circ f

, and so on. Composition in a category and the identity morphism make the endomorphisms of a fixed object in a locally small category into a monoid. This packages repeated compatible operations, including irreversible ones, into a single structure.

The general language has a documented historical milestone in the 1945 paper of Samuel Eilenberg and Saunders Mac Lane. They defined categories of objects and compatible maps, and distinguished maps admitting inverses within that category. Their examples included groups, vector spaces, and topological spaces. This gave a common framework for compatible self-maps and their invertible cases. See Eilenberg and Mac Lane, General Theory of Natural Equivalences, pp. 234 and 237–239.

 Read the full article

Endomorphism of a finite cyclic group 2026-10-14

 View more

Every endomorphism of the additive finite cyclic group

C_{n} = Z / n Z

, for a positive integer

n

, has the form

f_{a} (k) = ak (mod n)

, determined by

a = f_{a} (1)

. This is the self-map case of homomorphism from a finite cyclic group: repeated addition forces the value at every element. Conversely, each choice of

a

respects addition and gives a well-defined map on congruence classes.

Let

d = g cd (n, a)

, the greatest common divisor. The image of a group homomorphism is the cyclic subgroup generated by

a

, with size

n / d

by order of an element of a finite cyclic group. The kernel of a group homomorphism is

ker f_{a} = {0, n / d, 2 n / d, \dots, (d - 1) n / d}, ∣ ker f_{a} ∣ = d .

(1)

Indeed,

ak = 0 (mod n)

is equivalent to

n / d

dividing

k

, after cancelling

d

and using coprimality. Consequently

f_{a}

is a group automorphism exactly when

a

and

n

are coprime. In that case a modular inverse

b

a

gives

f_{a}^{- 1} = f_{b}

. This connects reversible self-maps directly to the generators of a finite cyclic group.^[ref]

 Read the full article

Exclusive or Created 2026-09-28 Updated 2026-10-20

 View more

Exclusive or returns one exactly when its two input bits differ. Its truth table gives

0 \oplus 0 = 0

0 \oplus 1 = 1

1 \oplus 0 = 1

, and

1 \oplus 1 = 0

. The identities

P \oplus Q = (P \lor Q) \land \neg (P \land Q) = (P \land \neg Q) \lor (\neg P \land Q)

(1)

express exclusive or using logical conjunction, logical disjunction, and logical negation. The first expression accepts at least one input and then excludes both; the second explicitly lists the two accepted input pairs.

For numerical bits, exclusive or is addition in modular arithmetic modulo two:

x \oplus y = (x + y) mod 2.

(2)

The binary operation is commutative and associative, because addition modulo two has those properties. It satisfies

x \oplus 0 = x

x \oplus 1 = \neg x

, and

x \oplus x = 0

. These identities explain why a bit can be toggled and restored with the same operation.

On binary strings of equal length, bitwise exclusive or applies the one-bit rule separately at each position. For example,

1010 \oplus 0110 = 1100, 1100 \oplus 0110 = 1010.

(3)

A bit mask of

0110

toggles exactly the middle two bits. Applying the mask twice restores the original binary string: each selected bit changes twice, and each unselected bit stays fixed. This positional operation is distinct from taking the exclusive or of the overall truth values of two integers.

 Read the full article

Field with four elements Created 2026-10-06 Updated 2026-10-14

 View more

Build this finite field by taking a quotient ring of a polynomial ring:

F_{4} = F_{2} [t] / (t^{2} + t + 1), α = [t] .

(1)

The polynomial

f (t) = t^{2} + t + 1

has

f (0) = f (1) = 1

in the prime field

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 α

, with

a, b \in F_{2}

: precisely

0, 1, α, α + 1

The defining relation is

α^{2} + α + 1 = 0

. Since this finite field has characteristic two, every element equals its additive inverse, and the relation becomes

α^{2} = α + 1

. Addition acts separately on the two coefficients:

(a + b α) + (c + d α) = (a + c) + (b + d) α .

(2)

All coefficient calculations use modular arithmetic modulo two. For example,

(α + 1) + α = 1

and

(α + 1) + (α + 1) = 0

. Encoding

a + b α

as the pair of bits

(b, a)

gives

0 \leftrightarrow 00

1 \leftrightarrow 01

α \leftrightarrow 10

, and

α + 1 \leftrightarrow 11

; addition is bitwise exclusive or. These are coordinates in the basis

1, α

, so the label

10

does not make

α

the element

1 + 1

For multiplication, expand using the distributive property and replace every

α^{2}

α + 1

(a + b α) (c + d α) = (a c + b d) + (a d + b c + b d) α .

(3)

For example,

α (α + 1) = α^{2} + α = 1

, while

(α + 1)^{2} = α^{2} + 1 = α

. 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.

Figure 1.
Computed addition and multiplication tables for the field with four elements
. **Details**.

The nonzero multiplicative inverses are

1^{- 1} = 1

α^{- 1} = α + 1

, and

(α + 1)^{- 1} = α

. Consequently the equation

αx = α + 1

has the unique solution

x = (α + 1)^{2} = α

. Repeated multiplication gives

α^{0} = 1

α^{1} = α

α^{2} = α + 1

, and

α^{3} = 1

. They cycle through every element of the multiplicative group of a finite field.

Compare the ring

Z /4 Z

, also with four elements. Its addition satisfies

1 + 1 = 2 \neq = 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

α

instead rotates the three nonzero elements, preserving their distinctness. The figure makes visible why counting four elements alone does not specify their arithmetic.

Figure 2.
Four elements with different arithmetic: a field and integers modulo four
. **Details**.

 Read the full article