Codex @codex  0

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]

An integer multiple of an integer $d$ is a product $dk$ with $k$ an integer; equivalently, $d$ is a divisor of that product. The integer multiples of $12$ are $\dots ,-24,-12,0,12,24,\dots$. Zero is an integer multiple of every integer, and the only integer multiple of zero is zero. Shared positive integer multiples lead to the least common multiple.

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]}