Division algorithm

A division algorithm is an algorithm that computes the quotient and remainder of two integers. Its success is guaranteed by the following theorem:

For any two integers $n$ and $d$, where $d > 0$, there exist unique integers $q$ and $r$, with $0 \leq r \leq d - 1$, such that: $$n = qd + r$$ This formalizes integer division. You can write $q$ and $r$ in terms of $n$ and $d$ with the $\text{div}$ and $\bmod$ operations: $$n = (n \text{ div } d) \times d + (n \bmod d)$$

In other words, any integer $n$ can be uniquely expressed as a linear combination of some quotient $q$ and remainder $r$, for every given positive divisor $d.$ Likewise, if you isolate the remainder $r$, it becomes a linear combination of $n$ and $d.$ The Euclidean algorithm is based on this fact.

Anyway, let's look at a specific division algorithm that will describe exactly how $q = n \text{ div } d$ and $r = n \bmod d$ are computed. It takes the form of repeated subtraction and depends on the sign of the dividend:

algorithm division is
    input: two integers, n and d, where d > 0
    output: two integers, q = n div d and r = n mod d

    q ← 0
    r ← n
    if n ≥ 0 (the non-negative case)
        while r ≥ d
            q ← q + 1
            r ← r - d
    else (the negative case)
        while r < 0
            q ← q - 1
            r ← r + d

So, if you ever find yourself confused on how to compute $\bmod$, no worries. You can trust that this algorithm will always be correct.

⚠ Notice that this algorithm is consistent with the theorem above, ensuring that $r$, the result of $n \bmod d$, will always be a non-negative integer less than $d.$ Perfect!

⚠ Here's a fact that might come in handy someday. For every positive integer $n$, if $d$ divides $n$, then there are exactly $\frac{n}{d}$ positive integers less than or equal to $n$ that are also divisible by $d.$

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort