= Divisibility
{title2=$\mid$}
{wiki}
For <integers> $d,n$, \b[$d$ divides $n$] when <multiplication> by some <integer> $k$ takes $d$ to $n$:
$$
d\mid n\quad\Longleftrightarrow\quad \text{there exists }k\in\mathbb Z\text{ such that }n=dk.
$$
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\ne0$, 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\mid12$ because $12=3\cdot4$, whereas $5\nmid12$ because $12=5\cdot2+2$. Signs do not change <divisibility>: $-3\mid12$ 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\cdot0$. In particular, \b[$0\mid0$]; however, $0\nmid n$ whenever $n\ne0$, 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\cdot1$, and a <transitive relation>: if $b=ar$ and $c=bs$, then $c=a(rs)$. Moreover, a shared <divisor> divides every <integer> <linear combination>:
$$
d\mid a,\quad d\mid b\quad\Longrightarrow\quad d\mid(ax+by)\qquad(x,y\in\mathbb Z).
$$
Indeed, writing $a=du$ and $b=dv$ gives $ax+by=d(ux+vy)$. For example, $6\mid12$ and $6\mid18$ 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\mid3$ 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. https://geometor.github.io/euclid/heath/VII/index.html[Euclid, Elements VII, definitions 3 and 5, T. L. Heath translation]{ref}
Back to article page
