After the reduction in part (b), multiply by . The new bottom-left entry is , whose absolute value is strictly smaller than the previous :
Repeated Euclidean division must terminate because the nonnegative integers decrease strictly until zero. Thus a word in and their inverses gives a matrix with bottom-left entry zero. Its determinant is one, so the diagonal entries are equal and are either both or both :
Since , this final matrix belongs to . So does , proving
A suitable precondition, including the empty array case, is
A base of one is allowed: its only valid digit is zero. The empty product is one, so permits exactly . Each Euclidean division extracts the next least significant digit.
def intToDigs(n: Int, bs: Array[Int]): Array[Int] = {
  // Pre: every base is positive, and 0 <= n < product(bs).
  val N = bs.length
  val xs = new Array[Int](N)
  var i = 0
  var q = n
  while (i < N) {
    xs(i) = q % bs(i)
    q = q / bs(i)
    i += 1
  }
  xs
}
The expensive precondition is a caller obligation, rather than a separately computed product inside the conversion. Define . The loop invariant is
together with for each processed digit. The Euclidean division identity proves preservation of the reconstruction equality. Positivity of the bases gives the digit bounds and the next bound on the quotient. The loop variant is . At exit, forces , hence
There are exactly remainder operations and divisions, hence counted operations. The returned array occupies space and the remaining auxiliary space is constant. A represented value can never exceed , as follows either by the same nested expansion or by telescoping ; thus the stated range is also necessary for positive bases.
Write using the Euclidean division. If and , then . Conversely, if and , then . Therefore and have exactly the same positive common divisors, proving
For , this agrees with .
By Euclidean division, write and , with integers and . The hypothesis is . Apply the addition rule from part (b)(i) with to obtain
Therefore . But , and the only multiple of in that interval is zero. Hence
so the two remainders agree.
We prove the contrapositive. If , Euclidean division gives or for an integer . Squaring gives respectively or . Both have remainder upon division by , so . Taking the contrapositive yields .
Use the Euclidean algorithm with floor quotient and nonnegative remainder, including for a negative numerator:
PROCEDURE rat2cf(n, d: INTEGER): fraction;
VAR q, r: INTEGER; p: fraction;
BEGIN
  q := n DIV d; r := n MOD d;
  NEW(p); p.head := q; p.tail := NIL;
  IF r # 0 THEN p.tail := rat2cf(d, r) END;
  RETURN p
END rat2cf;
For , Euclidean division gives with . If , the singleton [q] is exact. Otherwise
so the recursive tail represents . Its numerator is positive and greater than its denominator, so every tail head is a positive integer. The new denominator is strictly smaller than , proving algorithm termination by descent through the positive integers.
The returned list represents exactly . For example gives [-3,1,2]; truncating negative division toward zero would violate the required positivity of the tail. There are Euclidean algorithm steps, with output allocation and recursive stack depth linear in the number of generated nodes.
Positional notation Created 2026-09-29 Updated 2026-10-14
In positional notation, a numeral digit contributes its value multiplied by a weight determined by its position. Fix an integer radix . A finite string of numeral digits , with , represents the nonnegative integer
The rightmost position has weight ; each move left multiplies the weight by . This weight is the place value. For a nonzero integer, the canonical string has . Zero is written with the single numeral digit . Leading zeros are permitted in a fixed-width display but omitted in the canonical form: . A negative integer is written with a separate minus sign and the positional notation for its absolute value; the minus sign is not a numeral digit.[ref]
For example,
The zero is essential inside this string: , not . It records that the tens position contributes nothing while keeping the hundreds and units in their proper positions. The same integer has binary representation
Figure 1.
One integer, two encodings:
. Each numeral digit is multiplied by its place value. Decimal uses the weights ; binary uses . Zero digits preserve positions without contributing to the total. Both rows sum to . Details.
Repeated Euclidean division constructs the representation exactly. Set . At each step write
Keep the remainder and continue with the integer quotient . A positive quotient strictly decreases, so eventually it is zero. Substituting the successive equations back into the first gives : the numeral digits are obtained from right to left. The remainder modulo uniquely fixes , and then the quotient uniquely fixes the remaining string by the same reasoning. This proves existence and uniqueness once leading zeros are excluded. The needed unique quotient and remainder are precisely the conclusion of the Euclidean division theorem.[ref]
This finite expansion concerns nonnegative integers. Extending positional notation to fractional positions uses weights to the right of a point; an arbitrary real number need not have a finite digit string. In particular, the decimal representation represents , while the base-two string represents . The radix is part of the interpretation.
The benefit is compact arithmetic: positions can encode every nonnegative integer below . To see the upper endpoint, fill all positions with ; the finite geometric series gives . Carrying in addition exchanges units of one place value for one unit of the next. Thus a short string stores a large count and also supplies an algorithm for computing with it.
Quotient Created 2026-10-14 Updated 2026-11-05
The quotient of by a nonzero in a field is , the unique solution of . Thus is the rational quotient of by .
In Euclidean division of integers, the word instead denotes the integer in with a specified remainder range; for , . Here has quotient and remainder . Stating the ambient arithmetic prevents confusion between exact division and division with remainder.
Remainder 2026-10-14
For an integer and positive integer , the remainder in Euclidean division is the unique integer in for which with an integer . It is not the full quotient .
Residue class Created 2026-09-24 Updated 2026-10-14
For a positive integer modulus , the residue class of an integer is the equivalence class
It 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 , so there are exactly residue classes. When , there is just one, .
Define addition and multiplication of residue classes by
These definitions must give the same answer whichever integers represent the classes. If and modulo , then
Both differences are divisible by , proving that the operations are well-defined. For example, and , since . Replacing nine by gives the same answers with smaller intermediate integers.
With these operations the residue classes form the finite commutative ring , a quotient ring. It need not be a field: 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.
Turán graph Created 2026-09-29 Updated 2026-10-14
The Turán graph is a complete multipartite graph with independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when .[ref]
Figure 1.
The Turán graph has three independent sets of sizes , giving edges and no four-vertex clique
. Details.
In this example, the independent sets are , and . Count the edges between each pair of parts:
Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form . Conversely, every choice of one vertex from each part is a triangle in a graph, giving triangles in a graph. Clique exclusion here does not mean triangle-free.
For the exact count, Euclidean division writes , where uses the floor function and is the remainder, with . There are parts of size and of size . For any part sizes summing to , count cross edges by expanding the square:
Therefore
For , we have , giving . The Quadratic Turan edge bound gives instead: the exact correction subtracts .
Balancing is an integer optimization with a simple reason. If two part sizes satisfy , moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares by
so it increases the edge count by . For eight vertices, parts give edges; moving one vertex produces and edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.
Choose an original teaching model with 16-bit virtual addresses, 16-bit physical addresses, and 256-byte memory pages and page frames. The eight high bits identify a virtual memory page; divide these into two four-bit indices. The eight low bits are the offset within the memory page. Thus each page table has 16 entries: the root selects a lower-level page table, and that table selects a data page frame. Every page table entry is four bytes, including its reference and flags. These are chosen model parameters, not a hardware entry encoding.
For a virtual address , extract the root index , lower-level index , and offset by Euclidean division:
Here is the floor function and denotes the remainder in Euclidean division. Each index ranges from 0 to 15, and ranges from 0 to 255. In hexadecimal, virtual address 0x1234 splits into , , and ; its binary numeral system representation is 0001 | 0010 | 00110100.
Fix the requested operation to be a one-byte user read. Assume both table nodes and the data page frame are resident, table reads are allowed, and no mapping changes during the page table walk. The model requires presence at both levels and takes the set intersection of the two entries' read, write, execute, and user-access permissions. This is an explicit memory protection rule for this model; Sv39 page tables use different rules. The root's physical address is 0x8000; the relevant entries are:
RecordPhysical address of recordReference held in the page table entryPresence and permissions
Root entry 10x8000 + 1*4 = 0x8004Lower-level table at 0x9000Present; user; read/write; no execute
Lower-level entry 20x9000 + 2*4 = 0x9008Data page frame 0x07, base 0x0700Present; user; read-only; no execute
The first lookup obtains a table reference, not the final data physical address. The second lookup obtains page frame number 7. Both entries permit a user read, so the original offset is added to the data page frame base:
The page table walk therefore reads records at 0x8004 and 0x9008, then the requested read accesses data at 0x0734. All three are distinct physical addresses. These are two dependent table lookups followed by one data access, not a claim of three accesses to main computer memory: a memory cache can satisfy table lookups, and cached intermediate translations can skip them.
Figure 1.
The model's 4+4+8-bit address split and complete read translation from 0x1234 to 0x0734
. Details.
Under the same memory protection rule, a user write at 0x1234 fails because lower-level entry 2 denies writes, even though root entry 1 allows them. Clearing either entry's presence flag also prevents the access. An absent root entry stops the page table walk before any lower-level lookup. A page fault then requires the operating system to determine whether a permitted mapping needs storage or the access is invalid; absence alone does not establish demand paging eligibility.
With an empty translation lookaside buffer, the permitted read causes a TLB miss and this successful page table walk, with no page fault. If the resulting mapping and permissions are cached for the current address space, a later read at 0x1235 can use a TLB hit to reach 0x0735. A later write can cause a protection page fault on a TLB hit because the cached mapping remains read-only. Assume cached permissions are current; changing them requires the architecture's prescribed invalidation. A TLB miss describes a missing cached translation, while a page fault describes an access that cannot proceed under the translation or protection rules. [ref]