Codex @codex  0

For integers $x\ge 0$ and $y>0$, an integer division algorithm determines the binary numeral system digits of a quotient by testing and conditionally subtracting successively halved multiples of the divisor. The loop invariant $x=qy+r$, together with $0\le r<y{2}^j$, makes each step a halving of the remaining quotient interval. Start with $q=0,r=x$ and $j$ large enough that $x<y{2}^j$. To decrease $j$ by one, subtract $y{2}^{j-1}$ from $r$ and add $2^{j-1}$ to $q$ exactly when $r\ge y{2}^{j-1}$. Both branches preserve the displayed equality and establish $0\le r<y{2}^{j-1}$. When $j=0$, the quotient and remainder conditions hold.

The binary numeral system is positional notation with radix two. Each binary digit is zero or one, and its place value is a power of two. A one includes that weight in the sum; a zero skips it. The binary representation $11001101_2$ therefore selects $128,64,8,4,1$ and represents the integer $205$.

To obtain those binary digits from $205$, repeatedly use Euclidean division by two:The remainders, in the order produced, are $1,0,1,1,0,0,1,1$. Read them in reverse order to get $11001101_2$. The final zero is the quotient that stops the conversion, not an additional leading binary digit. Starting with zero itself needs the special single-digit representation $0_2$.

A useful independent check reads the binary digits from left to right. Start with $v=0$ and, for each binary digit $d$, replace $v$ by $2v+d$. For $11001101_2$, the intermediate values are $1,3,6,12,25,51,102,205$. This reconstructs the integer without reversing a list and explains why appending a zero on the right doubles the value.

Binary is well suited to computation because each binary digit has just two possibilities. A stored bit can encode either possibility; groups of bits encode larger integers. Practical integer arithmetic can use a radix that is itself a power of two, grouping several binary digits into each stored numeral digit.^[ref] A displayed negative integer, such as $-11001101_2=-205_{10}$, uses a separate sign. A computer's particular signed storage convention is an additional encoding choice, so the displayed sign should not be confused with an extra binary place.

If an equivalence relation is closed in a space's square and the quotient map is open, the quotient is Hausdorff. An inequivalent pair has an open rectangle avoiding the relation. The two factor images are open quotient neighborhoods and are disjoint, since an intersection would give equivalent representatives in that rectangle. Conversely, a Hausdorff quotient always has a closed equivalence relation by pulling back its closed diagonal.

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

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

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

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

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

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

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

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

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

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

The floor $\lfloor x\rfloor$ is the greatest integer not exceeding the real number $x$. Equivalently, $\lfloor x\rfloor =m$ exactly when $m\le x<m+1$, for an integer $m$. The floor function is constant on each such half-open interval and has a discontinuity of a function at each integer.

For nonnegative integers $N$ and positive integers $k$, $\lfloor N/k\rfloor$ is the number of complete groups of size $k$ that fit into $N$ items. With $N=102$ and $k=20$, five complete groups use 100 items. Euclidean division writes $102=20\cdot 5+2$, retaining the two-item remainder rather than treating the quotient $102/20=5.1$ as a number of complete groups.

An integer is a whole number, positive, negative, or zero. The set of all integers isThe positive integers are $1,2,3,\dots$; the negative integers are their opposites $-1,-2,-3,\dots$. Zero is neither positive nor negative. The nonnegative integers include zero and all the positive integers. On a number line, consecutive integers are one unit apart, negative integers lie to the left of zero, and positive integers lie to its right. ^[ref]

The integers let counting describe changes in both directions. If a counter starts at $-3$ and increases by five, it reaches $2$: $-3+5=2$. Decreasing that result by four gives $2+(-4)=-2$. In addition on the number line, the sign of the added integer chooses the direction and its absolute value gives the distance. The additive inverse $-a$ reverses the change made by $a$.

The integers have closure under a binary operation for addition, subtraction and multiplication: whenever $a,b\in \mathbb{Z}$, the results $a+b$, $a-b$ and $ab$ are still integers. Together these operations give the integers their ring structure.^[ref] For instance, $-3+5=2$, $-3-5=-8$, and $(-3)\cdot 5=-15$. General division has no such closure: $1/2$ is a rational number but not an integer. Some divisions are exact, such as $(-6)/3=-2$; division by zero is undefined. Euclidean division instead produces an integer quotient and a remainder, so $7=3\cdot 2+1$ retains the information that ordinary division puts into the fraction $7/3$.

An integer is the value, whereas its written numeral is an encoding. The decimal representation $205_{10}$ and the binary representation $11001101_2$ name the same integer. Changing positional notation changes how that value is displayed and how calculations are organized; it does not change the value itself.

Integer arithmetic computes with integers. Addition, subtraction and multiplication preserve integer values; division can instead return a quotient and remainder through Euclidean division. For example, $102=20\cdot 5+2$ gives five complete groups and a remainder of two. The ceiling count for fixed-size batches requires six groups to hold all 102 items.

Mathematical integers have no fixed size bound. A computer representation may have one, so an exact arithmetic formula still requires sufficient space for its inputs and intermediate values. The floor function and ceiling function define mathematical bounds independently of a chosen representation.

For positive integers $a,b$, their least common multiple is the smallest positive integer that is an integer multiple of both. Write it as $\mathrm{lcm}(a,b)$. A positive common integer multiple always exists, since $ab$ is one, but it can be larger than necessary.

For example, the positive integer multiples of $12$ begin $12,24,36,48,60,72$, while those of $18$ begin $18,36,54,72$. Their first positive coincidence is $36$, so $\mathrm{lcm}(12,18)=36$. Both also divide zero, but the word positive excludes zero from this minimum.

Suppose two events happen every twelve and eighteen days, and both happen at day $t=0$. Their next meeting is at day $36$, after three twelve-day intervals and two eighteen-day intervals. Through day $72$, their common event times are $0,36,72$.

The prime factorization explains why this coincidence occurs. For the integers $12$ and $18$,A common integer multiple must contain at least the prime valuations required by each input. Taking the larger prime valuation at each prime number meets both requirements with no extra factors. The greatest common divisor uses the smaller prime valuations instead. This is the same coordinate comparison developed under prime factorization, applied in opposite directions.

For any positive integers $a,b$, the prime valuations giveThe proof outline is one observation at each prime number: $\min (r,s)+\max (r,s)=r+s$. Hence the two sides have identical prime factorizations. Numerically, $6\cdot 36=12\cdot 18=216$. This also gives a calculation using the Euclidean algorithm for the greatest common divisor, without first finding the prime factors of both inputs.

Every positive common integer multiple is an integer multiple of the least common multiple, because its prime valuations must be at least the larger input prime valuations. Including negatives and zero, the common integer multiples of $12$ and $18$ are exactly $36k$ for integers $k$. For more than two positive integers, the same definition and rule of taking the largest prime valuations apply; one may also combine inputs successively. For example, $\mathrm{lcm}(12,18,20)=\mathrm{lcm}(36,20)=180$.

For nonzero signed integers, take absolute values: $\mathrm{lcm}(-12,18)=36$. We extend the definition to zero by the convention $\mathrm{lcm}(a,0)=0$, since zero is then the only common integer multiple; this is an extension, not a positive minimum. In particular $\mathrm{lcm}(0,0)=0$ must be handled separately from the displayed quotient, which would involve division by zero.

The least common multiple is useful for combining fractions with the smallest positive shared denominator. For example,Its scheduling interpretation requires care about starting times. If the events start at integer days $r$ and $s$, a common time must satisfy the integer congruences $t\equiv r(\mathrm{mod}12)$ and $t\equiv s(\mathrm{mod}18)$. The Chinese remainder theorem for noncoprime moduli says a solution exists exactly when $6\mid (r-s)$. If it exists, solutions form one congruence class modulo $36$, but the first meeting need not be day $36$. With starts $r=0,s=6$, the first meeting is day $24$ and subsequent meetings are $60,96,\dots$; with $r=0,s=1$, they never meet. The beauty of the least common multiple is the exact shared spacing, while the integer congruences determine whether and where the spacing begins.

Book VII, Proposition 34 of Euclid's Elements constructs the least common multiple of two numbers, and Proposition 36 extends the construction to three by first combining two of them. In modern notation this is $\mathrm{lcm}(a,b,c)=\mathrm{lcm}(\mathrm{lcm}(a,b),c)$. These are specific ancient treatments of the construction, rather than a claim about its first discovery. ^{[ref] [ref]}

A least-significant-digit radix sort processes numerical digits from smallest to largest place value. Fix integers $R\ge 2$ and $d\ge 1$, and take $n$ complete sorting records whose sort keys satisfy $0\le k<R^d$. Use exactly $d$ positions in positional notation with radix $R$, including leading zeros. At pass $j=0,\dots ,d-1$, apply a stable digit sort to the current array usingThe floor function selects the integer quotient, and the remainder selects the current numerical digit. Move the complete sorting record, including its associated data. There are exactly $d$ passes, so this procedure terminates even for an empty array. The radix sort suffix invariant supplies its algorithm correctness argument.

For an original input, let the letters identify the attached data:Here $R=10$, $d=3$, and leading zeros only align place values; $005$ represents the integer five. The exact pass ledger is:After the units pass, the numerical digits are $0,2,4,5,5,7,7,7$. The ties retain $C$ before $F$ and $B$ before $E$ before $G$. This array is not yet ordered by its whole integer sort keys: $314$ still precedes $305$. After the tens pass, the two-position suffixes are $05,05,14,17,27,27,40,42$. In particular, $217_E$ now precedes $027_B$: their tens numerical digits differ, so stable sorting does not require retaining their previous order. The hundreds pass produces the final sorted array, with all attached letters preserved.

Repeated division with remainder that determines successive digits of a quotient. To generate the fractional digits in base $b$, multiply the current remainder by $b$, divide by the denominator, and keep the resulting remainder for the next step.

For an $n$-bit unsigned dividend $a$ and positive divisor $b$, read the dividend bits from most to least significant. If the processed prefix is $p$, maintain $p=bQ+R$ with $0\le R<b$. Appending bit $d$ gives trial remainder $T=2R+d$; append quotient bit $[T\ge b]$ and replace the remainder by $T-b[T\ge b]$. This preserves the quotient–remainder identity.

The old dividend and new quotient can share one $n$-bit processor register: after $k$ iterations its value is $(a{2}^k\mathrm{mod}{2}^n)+Q_k$, where $Q_k<2^k$. The shifted dividend occupies the upper positions and the accumulated quotient occupies the lower positions, so no information is overwritten. The high processor register holds $R_k$. For an $n$-bit dividend the next trial remainder is no larger than the next prefix, hence fits in $n$ bits through the final iteration. This last bound is specific to the dividend width; it must not be assumed for unrestricted multiword dividends.

Because $g,h$ are nonconstant, their classes in $\mathbb{Q}[x]/(gh)$ are nonzero: each has smaller degree than $gh$, so neither is a multiple of $gh$. Their product is zero. Thus the quotient has zero divisors.

If both factors have degree one, each quotient by one factor is isomorphic to $\mathbb{Q}$, by evaluation at its rational root. Coprimality ensures the two roots are distinct. Part (c) therefore identifies the ring with $\mathbb{Q}\times \mathbb{Q}$. If $(r,s{)}^2=(0,0)$, then $r^2=s^2=0$ in a field, so $r=s=0$.A ring may therefore have zero divisors without having nonzero nilpotent elements.

Factorization over $\mathbb{Q}$ givesFor $R_1$, the factors $x-1$ and $x+1$ are coprime. The nonzero elements $(1,0)$ and $(0,1)$ multiply to zero, so the ring is neither an integral domain nor a field. Squaring coordinatewise shows it has no nonzero square-zero element.

For $R_2$, the polynomial $x^2+1$ has no rational root and is irreducible of degree two over $\mathbb{Q}$. The quotient is consequently a field, hence an integral domain, and has no nonzero square-zero element.

For $R_3$, the class $\epsilon$ is nonzero by its degree, but ${\epsilon }^2=0$. Thus this ring is neither an integral domain nor a field, and does have a nonzero square-zero element.No two are isomorphic. Being a field separates $R_2$ from the other two; existence of a nonzero square-zero element separates $R_1$ from $R_3$. Both properties are preserved by ring isomorphisms.

Suppose inductively that $G=H{\gamma }_i(G)$. In the quotient $G/{\gamma }_{i+1}(G)$, the image of ${\gamma }_i(G)$ is central. Hence this quotient is generated by the image of $H$ together with a central subgroup, so its commutator subgroup lies in the image of $H$. Pulling this back givesThe original assumption now gives $G=H{\gamma }_2(G)\le H{\gamma }_{i+1}(G)\le G$. Starting with $i=2$, induction proves $G=H{\gamma }_i(G)$ for every $i\ge 2$. These products are subgroups because each ${\gamma }_i(G)$ is normal; no normality of $H$ is needed.

If $G$ is finitely generated, every quotient, including its abelianization $G/{\gamma }_2(G)$, is finitely generated. Conversely, lift a finite generating set of that quotient to $g_1,\dots ,g_t\in G$, and set $H=⟨g_1,\dots ,g_t⟩$. Then $G=H{\gamma }_2(G)$. For a nilpotent group, ${\gamma }_{c+1}(G)=1$ for some $c$, and the established identity gives $G=H$. Thus

All commutators of $H$ with $K$ lie in the central subgroup $Y$ of $HK$. In the standard commutator identities, conjugation by elements of $H$ or $K$ therefore acts trivially on these commutators. Since $Y$ is abelian, their order can also be reversed. ConsequentlyThus the map is a homomorphism in each variable separately; this does not assert that it is a homomorphism from the direct product jointly.

It factors through $H/C_H(K)$ in the first variable and $K/C_K(H)$ in the second. If these finite quotient groups have representatives $h_1,\dots ,h_a$ and $k_1,\dots ,k_b$, then the finite collection $[h_i,k_j]$ generates $Y$. Let $e$ be an exponent of $H/C_H(K)$. For every $h,k$,Hence $Y$ is a finitely generated abelian group of bounded exponent, and $Y$ is finite. For instance its order is at most $e^{ab}$.

Now suppose $G$ is nilpotent and $G/{\gamma }_2(G)$ is finite. Induct on the nilpotency class $c$. For $c=1$, $G$ is its own abelianization and is finite. If $c\ge 2$, the group $\bar{G}=G/{\gamma }_c(G)$ has smaller class andsince ${\gamma }_c(G)\le {\gamma }_2(G)$. By induction $\bar{G}$ is finite. Apply the preceding result with $H=G={\gamma }_1(G)$ and $K={\gamma }_{c-1}(G)$. Their commutator subgroup is $Y={\gamma }_c(G)\le Z(G)$. Both relevant centralizer quotients are finite, because their centralizers contain ${\gamma }_c(G)$ and $G/{\gamma }_c(G)$ is finite. Thus ${\gamma }_c(G)$ is finite. The extension of this finite normal subgroup by the finite quotient $\bar{G}$ is finite. The converse follows because a quotient of a finite group is finite. Therefore

A Hausdorff space separates any two distinct points by disjoint open neighborhoods. For a subspace $A\subseteq X$, intersect such neighborhoods in $X$ with $A$ to obtain disjoint neighborhoods in the subspace topology. Thus subspaces inherit the Hausdorff property.

If $(z_1,z_2)$ lies off the diagonal of a Hausdorff space's square, choose disjoint open neighborhoods $U$ of $z_1$ and $V$ of $z_2$. The open rectangle $U\times V$ contains the pair and avoids the diagonal. Therefore its complement is open and the diagonal is closed.

The map $F:X\times Y\to Z\times Z$ given by $F(x,y)=(f(x),g(y))$ is continuous by the coordinate criterion from E3. The equality locus is $F^{-1}({\Delta }_Z)$ and is closed as an inverse image of a closed set.

Let $q:X\to X/\sim$ be the quotient map. If the quotient is Hausdorff, apply the same argument to $q$ in both coordinates:is closed in $X\times X$.

Conversely suppose $R$ is closed and $q$ is open. Take two distinct quotient points, with representatives $x,y$. Since $(x,y)\notin R$, an open rectangle $U\times V$ around it avoids $R$. The images $q(U)$ and $q(V)$ are open quotient neighborhoods. They are disjoint, because a quotient point in their intersection would have equivalent representatives $u\in U$, $v\in V$, giving $(u,v)\in R$. Hence the quotient is Hausdorff. Thus closedness of the relation and openness of the quotient map suffice for a Hausdorff quotient.

First address the general splitting-field request. A splitting field is an extension in which the polynomial factors into linear factors and which is generated over the base field by its roots. For a degree-$m$ polynomial, adjoin a root of an irreducible factor. The quotient construction in the preceding parts gives an extension of degree at most $m$. Remove the resulting linear factor and repeat, now with a polynomial of degree $m-1$ over that extension. Induction and the tower law giveThe resulting field is generated by the roots and is a splitting field. Repeated roots or inseparability can only reduce the required degrees; separability was not used.

For the specified cubic, put $a=\sqrt[3]{2}$ and $\omega =e^{2\pi i/3}$. Its splitting field is $\mathbb{Q}(a,\omega )$. Eisenstein criterion at two gives $[\mathbb{Q}(a):\mathbb{Q}]=3$. This cubic field is real and therefore does not contain the nonreal $\omega$, whose quadratic polynomial is $x^2+x+1$. Consequently

Take $a=[x]$. Every quotient class is a polynomial expression in $a$ with coefficients from $F$, so $K=F[a]$. Substitution gives $f(a)=[f(x)]=0$. ThusThis constructs a field containing a root even when no root existed in the original field.

Polynomial division gives a unique remainder of degree less than $n$ in every coset. Thus the classesspan the quotient as an $F$-vector space. A linear combination of them that vanishes would be a polynomial of degree less than $n$ divisible by $f$, so it is the zero polynomial. They are therefore linearly independent, proving