# Natural-number divisibility: deciding by a multiplier witness, handling zero, and proving transitivity

[← Guide index](https://ocme.evemisslab.com/en/derivations/) · [Original MKO](https://ocme.evemisslab.com/en/mko/mko-natural-divisibility/)

This is an owner-adopted natural-language teaching guide. Finite/arithmetic checks are not universal proofs; no Lean was run, and review scope is recorded per revision. Original source status labels are retained as historical data. Formulas retain exact TeX; no new semantic AST is invented.

derivation-mko-natural-divisibility-01 · production-20261019-adopted-96



## Goal and scope

From the MKO's definition (a∣b ⇔ there is a natural k with b=a·k): (1) prove 6∣84; (2) prove 6∤87; (3) prove 4∤10, although 10/4=5/2 is a number; (4) prove that every a divides 0; (5) prove 0∣b ⇔ b=0, and explain why the witness for 0∣0 is not unique and why 0∤5; (6) prove that for a>0 there is at most one witness (and when a∣b that existing witness is unique); (7) prove reflexivity and transitivity of divisibility, and from 3∣6 and 6∣84 find a witness for 3∣84.

Works in the natural numbers including 0 (MKO assumption a1), with natural witnesses only (a2). To decide the case a>0, the guide proves 'a∣b ⇔ the remainder is 0' from the division algorithm (a cited prerequisite). Divisibility of negative integers, greatest common divisors and primes are not treated; the canonical MKO and its English edition are not changed.





## Givens and symbols


- division_algorithm
- order_basics
- mul_zero
- mul_assoc
- numeric_evaluation


- G1 — ℕ includes 0; multiplication is natural-number multiplication, and sums and products of naturals are natural (MKO assumption a1).
- G2 — The witness k must be a natural number; a noninteger quotient is not a witness (MKO assumption a2).
- G3 — Pairs to decide: (6,84), (6,87), (4,10), (3,6), (0,0), (0,5).


- a\mid b — a divides b
- a\nmid b — a does not divide b
- k — the multiplier witness, which must be natural
- b\bmod a — the remainder of b on division by a (a>0)
- \mathbb{N} — the natural numbers, including 0





## Rules and sources


- division_algorithm · prerequisite — Division algorithm: for an integer a and a positive integer b there are unique integers q, r with a=bq+r and 0≤r<b.
- order_basics · prerequisite — Order of the reals: exactly one of u<v, u=v, u>v holds; u<v and v<w give u<w; u<v gives u+w<v+w; u<v and w>0 give uw<vw; u<v and w<0 give uw>vw.
- mul_zero · prerequisite — Multiplying by zero: u·0=0. Reason: u·0=u·(0+0)=u·0+u·0; subtracting u·0 from both sides gives 0=u·0.
- mul_assoc · prerequisite — Associativity of multiplication: (uv)w=u(vw).
- numeric_evaluation · prerequisite — Exact evaluation of an explicit integer or rational expression; independently recomputable.
- def_unfold · prerequisite — Unfolding a definition: replacing a defined term by its definition (or folding it back) does not change whether a statement is true.
- exists_intro · prerequisite — ∃-introduction: if some a∈D satisfies P(a), then ∃x∈D, P(x).
- contradiction · prerequisite — Proof by contradiction: if assuming ¬P leads to a contradiction (a statement and its negation both hold), then P holds.
- add_zero · prerequisite — Additive identity: u+0=u.
- mul_inverse_nonzero · prerequisite — Inverse of a nonzero number: in ℚ, ℝ or ℂ, if u≠0 there is 1/u with u·(1/u)=1, and v/u means v·(1/u). 0 has no inverse, so v/0 is undefined.
- frac_rules · prerequisite — Fraction rules (all denominators nonzero): a/c+b/c=(a+b)/c; (a/b)(c/d)=(ac)/(bd); (a/b)/(c/d)=(ad)/(bc) (also needing c≠0); a/b=(ak)/(bk) for k≠0.
- forall_intro · prerequisite — ∀-introduction (generalization): if a statement is proved for an arbitrary element x, with no extra assumption on x, it holds for every x in the domain.
- mul_comm · prerequisite — Commutativity of multiplication: uv=vu (in commutative number systems such as ℤ, ℚ, ℝ, ℂ).
- case_analysis · prerequisite — Proof by cases: if P∨Q holds and both P⇒R and Q⇒R are proved, then R holds. The cases must cover every possibility.
- mul_one · prerequisite — Multiplicative identity: 1·u=u.
- exists_elim · prerequisite — ∃-elimination: from ∃x∈D, P(x) we may name some element a with P(a) by a fresh name; reasoning with a is allowed as long as the final conclusion does not mention a.
- eq_replace · prerequisite — Replacement of equals: an expression inside a statement may be replaced by an equal expression without changing whether the statement is true.
- forall_elim · prerequisite — ∀-elimination (instantiation): if ∀x∈D, P(x) holds and a∈D, then P(a) holds.
- mko_dvd_def · cited — For natural numbers a and b, a∣b exactly when there is a natural number k such that b=a·k. · mko-natural-divisibility
- nat_discrete · prerequisite — Naturals have no values in between: for naturals k and n, either k≤n or k≥n+1.
- L_rem_test · lemma — For a natural b and a positive natural a: a∣b ⇔ the remainder r of b on division by a is 0.





## Main derivation

S01 · definitionBefore

a\mid b

After

\exists k\in\mathbb{N}:\ b=a\cdot k

Conditions: a,b\in\mathbb{N}

Rule: mko_dvd_def · Uses: G1, G2, mko_dvd_def

Leaf basis: mko_dvd_def + def_unfold

By the MKO's definition, a∣b means there is a natural number k (a multiplier witness) with b=a·k. To prove a∣b one must exhibit such a k; to prove a∤b one must show that no natural k works.



S02 · impliesBefore

84=6\cdot 14,\ 14\in\mathbb{N}

After

6\mid 84

Conditions: none

Rule: exists_intro · Uses: S01, G3

Leaf basis: exists_intro + numeric_evaluation

6·14=84 (N1) and 14 is natural, so k=14 is a witness and 6∣84.



S03 · equivalentBefore

a\mid b\quad(a>0)

After

b\bmod a=0

Conditions: a>0

Rule: L_rem_test · Uses: S01, L_rem_test

Leaf basis: division_algorithm + exists_intro + order_basics

For a>0, divisibility can be decided by the remainder: by Lemma L_rem_test (proved in S03.1 to S03.3), a∣b exactly when the remainder of b on division by a is 0. This replaces 'search for a witness' by one recomputable division with remainder.



S04 · impliesBefore

87=6\cdot 14+3,\ 0\le 3<6

After

6\nmid 87

Conditions: 6>0

Rule: L_rem_test · Uses: S03, G3

Leaf basis: division_algorithm + nat_discrete + order_basics + numeric_evaluation

The remainder of 87 on division by 6 is 3≠0 (N2, N3), so by the equivalence of S03, 6∤87. A direct check agrees: 6·14=84<87<90=6·15, and every natural k has k≤14 (then 6k≤84) or k≥15 (then 6k≥90), so no k gives 6k=87. In the rationals 87/6=29/2=14.5, which is not natural.



S05 · impliesBefore

10=4k,\ k\in\mathbb{N}\ ?

After

4\nmid 10

Conditions: 4\neq 0

Rule: mul_inverse_nonzero · Uses: S01, S03, G2

Leaf basis: mul_inverse_nonzero + frac_rules + numeric_evaluation

In the rationals the only solution of 4k=10 is k=10/4=5/2 (division is allowed since 4≠0). 5/2 is not natural, so by G2 it is not a witness; there is no natural witness, and 4∤10. Check with S03: 10=4·2+2 with remainder 2≠0, the same conclusion.



S06 · impliesBefore

a\in\mathbb{N}

After

0=a\cdot 0,\ \text{so}\ a\mid 0

Conditions: none

Rule: exists_intro · Uses: S01, mul_zero

Leaf basis: mul_zero + exists_intro + forall_intro

For any natural a, a·0=0 and 0 is natural, so k=0 is a witness and a∣0. a was arbitrary, including a=0.



S07 · equivalentBefore

0\mid b

After

b=0

Conditions: none

Rule: mul_zero · Uses: S01, mul_zero

Leaf basis: mul_zero + mul_comm + exists_intro

0∣b means there is a natural k with b=0·k. But 0·k=0 for every k, so this says exactly that b=0.



S08 · impliesBefore

0=0\cdot 0=0\cdot 5,\quad 5\neq 0

After

0\mid 0\ \text{with non-unique witness};\ 0\nmid 5

Conditions: none

Rule: mul_zero · Uses: S07, G3

Leaf basis: mul_zero + numeric_evaluation

0∣0 holds, and both k=0 and k=5 are witnesses (0·5=0, N9), so the witness is not unique. Since 5≠0, S07 gives 0∤5. So 'zero never divides any number' is wrong: 0∣0 is true.



S09 · impliesBefore

b=a k=a k',\ a>0,\ k,k'\in\mathbb{N}

After

k=k'

Conditions: a>0

Rule: order_basics · Uses: S01, order_basics

Leaf basis: order_basics + case_analysis + contradiction

By trichotomy exactly one of k<k′, k=k′, k>k′ holds. If k<k′, then a>0 gives ak<ak′, contradicting ak=ak′; likewise for k>k′. So k=k′: an existing witness is unique, or equivalently there is at most one witness when a>0. This contrasts with the case a=0 in S08.



S10 · impliesBefore

a\in\mathbb{N}

After

a=a\cdot 1,\ \text{so}\ a\mid a

Conditions: none

Rule: exists_intro · Uses: S01, mul_one

Leaf basis: mul_one + mul_comm + exists_intro

Reflexivity: a·1=a and 1 is natural, so a∣a; this includes 0∣0 (0=0·1).



S11 · impliesBefore

a\mid b,\ b\mid c

After

a\mid c

Conditions: none

Rule: exists_elim · Uses: S01

Leaf basis: exists_elim + mul_assoc + exists_intro

Transitivity: from a∣b take a witness k with b=ak; from b∣c take a witness l with c=bl (S11.1). Substituting and using associativity gives c=a(kl), with kl natural (S11.2), so a∣c with witness kl.



S12 · impliesBefore

6=3\cdot 2,\ 84=6\cdot 14

After

84=3\cdot 28,\ 3\mid 84

Conditions: none

Rule: forall_elim · Uses: S11, G3

Leaf basis: forall_elim + numeric_evaluation

3∣6 has witness k=2 and 6∣84 has witness l=14; by S11, 3∣84 has witness kl=28. Check: 3·28=84 and 84 leaves remainder 0 on division by 3 (N10 to N12).



S13 · case_splitBefore

(a,b)\in\mathbb{N}^2

After

a=0:\ a\mid b\iff b=0;\quad a>0:\ a\mid b\iff b\bmod a=0

Conditions: none

Rule: case_analysis · Uses: S03, S07, S02, S04, S05, S08

Leaf basis: case_analysis + order_basics

Decision procedure: first check a=0, where a∣b ⇔ b=0 (S07); otherwise a>0 and a∣b ⇔ the remainder is 0 (S03). The two cases cover every natural a. Applied: (6,84) remainder 0, divides; (6,87) remainder 3, does not; (4,10) remainder 2, does not; (0,0) divides; (0,5) does not.







## Substeps and lemmas

S03.1 · impliesBefore

b=aq+r,\ 0\le r<a,\ q\in\mathbb{Z},\ b\ge 0

After

q\ge 0,\ \text{so}\ q\in\mathbb{N}

Conditions: a>0

Rule: order_basics · Uses: division_algorithm, order_basics

Leaf basis: division_algorithm + order_basics + contradiction

The division algorithm gives integers q and r. If q≤−1, then aq≤−a, so b=aq+r≤−a+r<−a+a=0, contradicting b≥0. Hence q≥0 and q is natural.



S03.2 · impliesBefore

b=aq+0,\ q\in\mathbb{N}

After

a\mid b

Conditions: r=0

Rule: exists_intro · Uses: S03.1, S01

Leaf basis: exists_intro + add_zero

(The ⇐ direction) If the remainder r=0, then b=aq with q natural (S03.1), so q is a witness and a∣b.



S03.3 · impliesBefore

b=a\cdot k,\ k\in\mathbb{N}

After

b\bmod a=0

Conditions: a>0

Rule: division_algorithm · Uses: S01, division_algorithm

Leaf basis: division_algorithm + add_zero

(The ⇒ direction) If b=ak, then b=a·k+0 with 0≤0<a. The quotient and remainder of the division algorithm are unique, so the remainder of b on division by a is 0 (and the quotient is k). S03.1 to S03.3 together prove Lemma L_rem_test.



S11.1 · impliesBefore

b=ak,\ c=bl

After

c=(ak)l

Conditions: none

Rule: eq_replace · Uses: S01, exists_elim

Leaf basis: eq_replace

Replace b in c=bl by the equal expression ak.



S11.2 · impliesBefore

c=(ak)l

After

c=a(kl),\ kl\in\mathbb{N}

Conditions: none

Rule: mul_assoc · Uses: S11.1, G1

Leaf basis: mul_assoc

Associativity gives (ak)l=a(kl); a product of naturals is natural (G1), so kl is a legitimate witness.







## Reverse audits


- S13 · sufficient_goal_reduction · S03, S07, case_analysis — Goal G: decide every pair correctly. Sufficient condition H: each of the cases a=0 and a>0 has a proved criterion; H⇒G by proof by cases. H is proved forwards in S03 and S07.
- S12 · premise_audit · S11, forall_elim, numeric_evaluation — An instance of S11 with a numeric check; it cannot replace the general proof.
- S11.2 · premise_audit · mul_assoc, G1 — It needs ℕ to be closed under multiplication; over the rationals this step would allow non-natural witnesses.
- S11.1 · premise_audit · eq_replace — Replacement of equals.
- S11 · premise_audit · S01, exists_elim, mul_assoc — The conclusion does not mention the temporary names k and l, so ∃-elimination is legitimate. No converse is claimed: a∣c does not give a∣b.
- S10 · premise_audit · mul_one, exists_intro — Only the multiplicative identity is used.
- S09 · premise_audit · order_basics, case_analysis — a>0 is needed to preserve strict inequality; for a=0 the conclusion fails (S08).
- S08 · premise_audit · S07, mul_zero — Two instances of S07 and one example of a non-unique witness.
- S07 · inverse_equivalence · mul_zero, exists_intro — Backward: if b=0, take k=0 to get b=0·0, so 0∣b. Both directions hold.
- S06 · premise_audit · S01, mul_zero, exists_intro, forall_intro — Only multiplication by zero is used; it holds for every a, so the statement generalizes.
- S05 · premise_audit · S01, S03, G2, mul_inverse_nonzero — The argument relies on the rational solution being unique: if the only solution is not natural, there is no natural solution. Having a numerical quotient does not mean divisibility.
- S04 · premise_audit · S03, nat_discrete, order_basics — A negative answer must exclude every k; the equivalence of S03, or the two-sided squeeze with nat_discrete, does so. Checking a few values of k would not be enough.
- S03.3 · premise_audit · division_algorithm — The key is uniqueness in the division algorithm; existence alone would not let one representation determine the remainder. The lemma itself is not used.
- S03.2 · premise_audit · S03.1, exists_intro — Only the fact that q is a natural number is used; the lemma itself is not used.
- S03.1 · premise_audit · division_algorithm, order_basics — It needs a>0 and b≥0; this ensures the quotient can serve as a natural witness.
- S03 · inverse_equivalence · L_rem_test — Both directions of the lemma (S03.2, S03.3) are proved; the premise a>0 is what the division algorithm needs.
- S02 · premise_audit · S01, exists_intro, numeric_evaluation — Existence needs only one witness; uniqueness is not claimed here (see S09).
- S01 · premise_audit · G1, G2, mko_dvd_def — This step only unfolds the definition; the witness is restricted to naturals (G2), not rationals.





## Error controls and negative controls

Having a numerical quotient is not divisibilityThe misconception the MKO names: claiming a∣b because b/a is a number. 10/4=5/2 is a rational number, but the witness must be natural, so 4∤10 (S05). Decide by a natural witness or by whether the remainder is 0.

A divisor equal to zero does not make every divisibility claim falseThe other misconception the MKO names: ruling that zero never divides any number. By the definition 0∣b ⇔ b=0 (S07), so 0∣0 holds and 0∤5. Note that no 'division by 0' is performed; one only looks for a multiplier witness.

A negative answer must exclude every witnessTo prove 6∤87, trying k=14 and 15 is not enough; the remainder lemma or the squeeze with nat_discrete must exclude every k (S04). Likewise 6∣3 fails: in 3=6·(1/2) the factor 1/2 is not natural, and 3 leaves remainder 3 on division by 6.


- 4∣10 because 10/4=2.5 is a number → reject — The witness must be natural; 10=4·2+2 with remainder 2≠0.
- 0 divides no number → reject — 0=0·0, so 0∣0.
- 0∣5 → reject — For every k, 0·k=0≠5.
- 6∣3 because 3=6·(1/2) → reject — 1/2 is not natural; 3=6·0+3 with remainder 3≠0.
- The witness for 0∣0 is unique → reject — 0=0·0=0·5, so k=0 and k=5 are both witnesses.





## Result and limitations

6∣84 (witness 14); 6∤87 (remainder 3); 4∤10 (the only rational solution 5/2 is not natural; remainder 2); every a divides 0 (witness 0); 0∣b ⇔ b=0, so 0∣0 but 0∤5, and the witness for 0∣0 is not unique; for a>0 there is at most one witness, unique when it exists; divisibility is reflexive and transitive, and 3∣84 has witness 2·14=28.


- The division algorithm (existence and uniqueness) is cited as a prerequisite; this guide only derives the remainder criterion L_rem_test from it.
- Only ℕ is treated; divisibility among integers with negative values is out of scope.





## Verification and source binding

14 declared checks for this guide; only the listed expressions are covered.


- source commit: b28a5edbd46279b1db2a3f3f48bb3f447e18899f
- adopted source SHA-256: c7700b425af628e5a943830098f9039a8ba739a667d2577ec46189e0e2124324
- original source SHA-256: 1b68c27c071f5fe0cfe48fffd7605f00b4dfae82833e7c47a8a473157438e68f
- Lean: NOT_RUN · independent AI: NOT_MEASURED

[Same-source full JSON (formulas, ASTs, controls and revision log)](https://ocme.evemisslab.com/data/derivations/production-20261019/guides/derivation-mko-natural-divisibility-01.json)